53. 最大子数组和 (opens new window)

1.动态规划

定义dp[ i ]表示以nums[ i ]结尾的最大子数组和。状态转换方程如下

• 如果当前dp[ i-1 ]小于零，那么dp[ i ]就等于nums[ i]。如果加了前一个结果就会比nums[ i ]小
• 如果当前dp[ i-1 ]大于零，那么dp[ i ]就等于nums[ i]+dp[ i-1 ]

讨论合理性：第i个元素是否纳入前一个连续子数组的问题，也就是说单独还是合并。

• 如果选择合并，那么nums[ i ]与dp[ i-1 ](记为a)合并是否一定是nums[ i ]能够合并的最大值？不妨假设前面有"另外一段子数组"和为b，与i元素合并后更大，也就是说b+nums[ i ]>a+nums[ i ]。然而前面的连续子数组要合并，肯定包含nums[ i -1]，根据dp数组的定义就有b=a。因此当前第i个元素如果选择合并，那么与dp[ i-1 ]合并得到的一定是能够合并的最大值。
• 如果前面的最大子数组和小于0，则不需要合并。

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];
        int max=dp[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=dp[i-1]<0?nums[i]:dp[i-1]+nums[i];
            max=Math.max(dp[i],max);
        }
        return max;
    }
}

2.贪心

考虑【-5，2，5】，子序列只能从2开始计算累加。前一个数如果为负数，甚至准确点是前一个连续子数组和如果为负数，那么再往下加只会拖累后面的连续子数组。因此此时只能新建一块连续子数组。

此处贪心贪的就是前一块连续子数组，只要它为负数那么才真正没有利用价值。这里贪心要有“块”的概念，而不能是“单个元素”的概念。比如【1000，-1，-1，1000】。只要前一个块还大于零，那么他就有与后面正数块合并的可能。

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