题目地址

先小结一下该类型的题目思考方向。该种类型题目都是当前情况的选择取决于之前的之前的情况（这种说法就很递归）。通常这个时候可以考虑一下之前的选择可能会有几种，属于是逆推思想。可以看下面的思路解析

思路1

1. 使用滑动窗口的思想解决
2. 在遍历到元素k的时候，之前的窗口值 value 会存在两种情况
   (1)窗口值 + k 变大
   (2)窗口值 + k 变小
3. 因为条件是要获取最大值，因此当属于总值升高的时候进行增加操作，总值下降的时候，因为前面的部分属于负增益，因此不需要进行累加，更新窗口值为当前值

class Solution {
    public int maxSubArray(int[] nums) {
        // 滑动窗口
        // 1. 左窗口滑动条件，当前窗口值<=0时移动左边界，说明前面的值加起来不能产生正收益
        // 1. 遇到正数加,
        //    如果之前的窗口值是负数,则更新窗口值为正数值
        //    如果之前的窗口值是正数,则更新窗口值为窗口值+正数值
        // 2. 遇到负数,
        //    如果负数+当前窗口值>=0,则更新窗口值为负数+当前窗口值
        //    如果负数+当前窗口值<0,则更新窗口值为当前值
        // 
        if (nums.length <= 1) return nums[0];
        int max = Integer.MIN_VALUE;
        int value = 0; //当前范围内总和
        for(int i : nums) {
            value = Math.max(i,value + i);
            max = Math.max(max, value); 
        }
        return max;
    }
}

思路2

1. 动归

Q.E.D.