第一反应是通过求出数组中的所有子数组。但是这样肯定不是最优解。
下面是优化的解法:
1.从头到尾逐个累加数字的和
2.当累加的数字存到一个变量currSum中，如果currSum小于0，则将其置为0。否则将其与另一个变量maxSum(记录目前为止遍历数组中最大和)比较，如果大于maxSum则更新maxSum。
3.进行一次遍历后返回maxSum。该算法时间复杂度为O(n)。
1 public class 连续子数组的最大和 { 2 3 public static int FindGreatestSumOfSubArray(int[] array) { 4 if(array.length==0||null==array){ 5 return 0; 6 } 7 int maxSum = Integer.MIN_VALUE; 8 int currsum = 0; 9 for(int i=0;i<array.length;i++){ 10 if(currsum<0){ 11 currsum = 0; 12 } 13 currsum += array[i]; 14 15 if(currsum>maxSum){ 16 maxSum = currsum; 17 } 18 } 19 return maxSum; 20 } 21 22 public static void main(String[] args) { 23 int[] nums = {-2,-8,-1,-5,-9}; 24 System.out.println(FindGreatestSumOfSubArray(nums)); 25 } 26 }
原文：https://www.cnblogs.com/blzm742624643/p/10412585.html