给定一个数组,求数组中最大连续子序列的和

时间复杂度为O(n)

只需要过一遍数组即可，但是需要深入理解这个数组的本质特征，即动态规划的方法。

首先设置两个变量，thisSum和maxSum。其中thisSum表示走到当前位置元素的和；maxSum表示走到当前位置下的连续子序列的最大和。

注意：如果thisSum为负，则直接将其置为0；如果thisSum大于maxSum，则将maxSum置为thisSum的值。

public static int maxSubArray(int[] nums)
 {
 int length = nums.length;
 if(length <= 0)
 return 0;
 int CurSum = 0;
 int max = Integer.MIN_VALUE;
 for(int i = 0; i < length; i++)
 {
 if(CurSum <= 0) //当当前的和小于等于0，那么就给其置为当前元素的值
 CurSum = nums[i];
 else
 CurSum += nums[i];
 if(CurSum > max)
 max = CurSum;
 }
 return max;
 }

推荐教程：PHP教程