【Leetcode】53.最大子数组和（前缀和）

leetcode-53.png

这一题用动态规划解体比较快，也比较容易理解
只需要求出最大的【和】即可，不需要求出【子数组】
至于求出【子数组】这种，在后面再做讨论
假设在第n个位置回出现最大的【和】，那么此时的解为

f(n) = nums[n] + f(n-1)

对于这个状态方程不难理解，即每次计算，我们都保存最大的数字，也就是f(n-1)

动态规划

题解如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int res = nums[0];
        for(int i = 1; i < length; ++i){
            if(nums[i-1] > 0){
                nums[i] += nums[i-1];
            }
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

对于给定数组，例如：

nums =  [-2,1,-3,4,-1,2,1,-5,4]
每次计算判断当前数字是否大于0，如果大于0，则跟下一位数进行相加
如果当前数字小于0，那么无论下一位数字是正还是负，都会导致相加之后的数字和变小，所以负数不能跟下一位相加
-2,1,-3+1,4,-1+4,-1+4+2,-1+4+2+1,-1+4+2+1-5,-1+4+2+1-5+4
-2,1,-2,4,3,5,6,1,5

对于上面这种解法，改变了原数组，下面这种解法思路一样，但是不会改变原数组
每次轮询到当前数字之后，会与pre相加，然后与当前的数字进行比较，保存较大的数字
跟上面的判断当前数字大于0之后再相加的思路一样。

动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int res = nums[0];
        int pre = 0;
        for(int i = 0; i < length; ++i){
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }
}

对于题目给定的数组，我们计算pre每次的数字为

-2,1,-3,4,-1,2,1,-5,4
0.pre = 0
1.pre = max(0-2,-2) = -2
2.pre = max(-2+1,1) = 1
3.pre = max(1-3,-3) = -2
4.pre = max(-2+4,4) = 4
5.pre = max(4-1,-1) = 3
6.pre = max(3+2,2) = 5
7.pre = max(5+1,5) = 6
8.pre = max(6-5,-5) = 1
9.pre = max(1+4,4) = 5

与上面计算过后的nums数组进行比较，pre的过程跟nums数组一一对应

贪心算法

保证sum累加时一直大于零，那么就可以累加出最大的数字和
一旦sum小于0的时候，那就是碰到一个“究极大”的负数，导致累加的sum变成负数，所以此时可以进行重置，也就是sum=0。

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < length; ++i){
            sum += nums[i];
            res = Math.max(sum, res);
            if(sum < 0){
                sum = 0;
            }
        }
        return res;
    }
}