输入一个整形数组(可能有正数和负数),求数组中连续子数组(最少有一个元素)的最大和。要求时间复杂度为O(n)(解决)

时间:2022-11-19 17:15:00

输入一个整形数组(可能有正数和负数),求数组中连续子数组(最少有一个元素)的最大和。要求时间复杂度为O(n)。


输入描述:
【重要】第一行为数组的长度N(N>=1)

接下来N行,每行一个数,代表数组的N个元素

输出描述:
最大和的结果

输入例子1:
8
1
-2
3
10
-4
7
2
-5

输出例子1:
18

思路:对输入的数组进行计算,

 

import java.util.Scanner;

public class Main {

public static void main(String[] args){
  Scanner in = new Scanner(System.in);
  int inputSize = in.nextInt();
  int[] array = new int[inputSize];

  for(int i=0;i<array.length;i++){
  array[i] = in.nextInt();
  }

  System.out.println(findMax(array,array[0]));

}

public static int findMax(int[]array,int maxSum){
  int localSum = 0;//存储当前的可能是目标子集的元素和
  int inputSize = array.length;
  for(int i =0;i<inputSize;i++){

  if(array[i]>0){//如果当前的元素大于0,则把它的值加入当前目标子集的和
    if(localSum<0){//如果localSum小于0,那么当前的子集必然不会构成目标子集
    localSum=0;
  }
  localSum+=array[i];
  }else {//如果当前的元素小于0,则要判断localSum是否大于0,如果大于0,则加入当前元素值(因为之后可能仍然有很大的数)
    if(localSum>0){
    localSum+=array[i];

    }else{//如果localSum小于0,说明之前的一些元素有比较大的负数,那么就从当前位置开始重新寻找,
      localSum = array[i];

    }
  }

  if(maxSum < localSum){
  maxSum = localSum;
  }
  }

  return maxSum;
  }

}