- 在LeetCode上做的一道题目，想了很久没有想出比较简便的方法，借鉴了网上的方法之后做了然后做个总结。
题目描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
简单而言就是找出一个正负数都有的数组中最大的子数组之和。
分析解答：
- 看到这个题，首先想到的一个最简单但是时间复杂度最高的方法就是，把这个数组的所有子数组的和都求出来，一个一个比较，取最大值。
假设数组的长度为n，那么以它的每个元素的下标i（i从0开始）为子数组起点，都有n-i个子数组，所以所有的子数组个数是
n+n-1+n-2+n-3+…+4+3+2+1
=(n+1)+(n-1+2)+(n-2+3)+...
=(n/2)(n+1)
所以时间复杂度为O（n²）； - 动态规划（复杂度为O(n)）。对于数组中第i个元素来说，设curSum为nums[i]之前的累加和最大值，如果这个最大值<0，那么加上nums[i]之后必然会使累加和变小。即curSum+nums[i]<nums[i]，所以此时应该丢掉之前的累加和，从nums[i]重新开始累加。反之，curSum+nums[i]>nums[i]，必定会使和变大（即便nums[i]为负数）。这样，每循环一个元素，都能保证去掉拖后腿的累加和。只要不拖后腿，能多加一个正数，肯定是有利于累加和的增大。从这些累加中比较出值大的累加和即可。
public static int maxSubArray(int[] nums){
int curSum = nums[0];//curSum为nums[i]之前的累加和最大值
int maxSum = nums[0];//最大累加和
int curBegin = 0;//当前累加和起点
int maxBegin = 0;//最大累加和起点
int maxEnd = 0;//最大累加和终点
for(int i=1;i<nums.length;i++){
if(curSum>0){
//如果之前的累加和>0，加上nums[i]元素
curSum += nums[i];
}else{
//否则，以nums[i]为起点重新开始
curSum = nums[i];
curBegin = i;
}
//如果当前累加和>记录的累加和，赋值。并将当前累加和的起终点记录下来
if(curSum > maxSum){
maxSum = curSum;
maxBegin = curBegin;
maxEnd = i;
}
}
System.out.println("起点:"+maxBegin+",终点:"+maxEnd);
return maxSum;
}
