连续子数组的思路与解析

多用两个数组来记录比较能理清楚思路，实际上这里又两个涉及到递推的地方，一个是连续前 n项和的极值，一个是连续前n项和的最大值。
假如题目变一下，前n项和的最小值，连续前n项和第二大的值

//我们要计算 dp[i],就先算dp[i-1],然后与我们的 sum[i] max 一下就可以了。
//要算 sum[i],就得先算 sum[i-1]，假如sum[i-1]>0, 那么 sum[i-1]+array[i]可能大于0，sum[i-1]<0,那么当前最大连续子数组就是 array[i] 这一个只有一个元素的子数组。
public int FindGreatestSumOfSubArray(int[] array) {
    int [] dp=new int [array.length]; // 记录截止当前索引的连续子数组最大和
    int [] sums=new int [array.length];//记录中间求和部分
    for (int i = 0; i < array.length; i++) {
        if(i==0){//初始化
            dp[i]=array[i];
            sums[i]=array[i];
        }else{
            if(sum[i-1]>0){
                sums[i]+=sum[i-1]+array[i];
//array[i] 默认为正数，只要前面和比0大，为什么要有这种考虑，因为假设前面和为 10，array[i]=-1,但是可能存在array[i+1]=15的的情况，这时候的最大值为 10+-1+15,所以不是比较array[i]的正负，而是比较sum[i-1]的正负
            }else{
//sum[i-1] 为负意味着，sum[i-1]+array[i]<array[i] ,所以这里的最大值直接更新为 array[i],前面的和可以直接清零了，于是从这里又开始算连续
                sums[i]=array[i];
            }
            dp[i]=Math.max(dp[i-1],sums[i]);
        }
    }
    return dp[array.length-1];
}

在做的过程中很容易把两种递推混起来了，比如我的第一次提交

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int [] sums=new int[array.length];
        for(int i=0;i<array.length;i++){
            if(i==0){
                sums[i]=array[i];
            }else{
                sums[i]=Math.max(sums[i-1],sums[i-1]+array[i]);
            }
        }
        return sums[array.length-1];
    }
}

这个其实就没有care 到 连续子数组的问题，这样出来只是计算整个数组元素和的最大值。需要有空间来存放临时的极值，然后更新极值