动态规划设计：最大子数组 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划设计：最大子数组

评论礼仪 见这里，违者直接拉黑。

[edgeowner]

状态方程有个条件少了，对于 特殊case [-2,1]这种就不行； 缺少一定条件的判断 if (dp[i - 1] > 0) { dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); } else { dp[i] = nums[i]; }

[super468]

如果dp[i - 1] <= 0，max函数返回的也是nums[i]。不需要额外判断

[ElandWoo]

这是不是一种贪心思想。

[DiamondI]

用一个变量就可以表示状态转移的过程了，因为最终求解的时候，旧状态是用过即弃的，不需要保留它。

换句话说，在状态压缩的题解代码里：

dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;

dp_1 其实没有什么存在的必要，因此上面的两句可以合并成一句：

dp = Math.max(nums[i], nums[i] + dp);

[ginward]

这个应该就是Kadane's algorithm

[cillian-bao]

其实本题可以利用滑动窗口去解决，每次记录了当前的最大值即可 缩小窗口的时机在sum<0时，因为此时该窗口肯定不会是所要求的。

class Solution
{
	public int maxSubArray(int[] nums) {
		int left=0;
		int right=0;
		int sum=0;
		int maxsum=nums[0];
		while(right<nums.length())
		{
			sum+=nums[right];
			if(sum<0)
			{
				sum-=nums[left];
				left++;
			}
			//进行答案的更新
			maxsum=Math.max(maxsum,sum);
		}
		//进行特殊情况的处理
		        int maxVal = nums[0];
        for (int i = 1; i <nums.size(); i++) {
            maxVal = max(maxVal, nums[i]); 
        }
        return maxVal < 0 ? maxVal : maxsum;
	}
}

[bert82503]

打卡，感谢！

[enthural]

以nums[i]结尾的最大子数组和情况之二和前面连成一个数组，但如何保证和前面的一定是连续的呢

[Maxiah]

本题的滑动窗口解法，重点在于maxSum的初始化

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 滑动窗口（快慢指针

        int left = 0, right = 0;
        int sum = 0, maxSum = INT32_MIN; // 重点：preMaxSum一定要设置为最小负数，这样遇到全负数组的时候才能不出错
        while(right < nums.size()){
            // 移入
            int c = nums[right];
            // 增大窗口
            right++;
            // 更新窗口
            sum += c;
            maxSum = sum > maxSum ? sum : maxSum;

            // 判断左侧窗口是否要收缩
            while(sum < 0){
                // 移除
                int d = nums[left];
                // 缩小窗口
                left++;
                // 更新窗口
                sum -= d;
            }
        }
        return maxSum;
    }
};

[mianbao374]

// 要么自成一派，要么和前面的子数组合并 dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); 我在想，如果数组是[4,5,-1,-1]，那岂不是最后dp[i]是7了？求解，我不知道是哪里看错了

[zclorne]

@mianbao374 没错，dp的定义就是以num[i]为结尾的[最大子数组和]，dp[n-1]确实是7，但是问题求的最终结果是dp数组的最大值max(dp[i])=dp[1]=9，你应该是看漏了

[buhubaiyu]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int subSum=0;
        int result=INT_MIN;
        for(int i=0;i<nums.size();i++){
            subSum=max(subSum+nums[i],nums[i]);
            result=max(result,subSum);
        }
        return result;
    }
};

[mianbao374]

@mianbao374 没错，dp的定义就是以num[i]为结尾的[最大子数组和]，dp[n-1]确实是7，但是问题求的最终结果是dp数组的最大值max(dp[i])=dp[1]=9，你应该是看漏了

明白了，是我看漏了

[labuladong]

确实，看了下评论区读者的讨论，本题可以用滑动窗口算法，我这两天把滑动窗口算法的思路补充到文章中

[oliyg]

有谁能给个 dp 函数的解法

[deepbreath373]

摩尔投票

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = 0;
        int res = Integer.MIN_VALUE;
        for(int num : nums){
            if(sum < 0){
                sum = num;
            }else{
                sum += num;
            }
            res = Math.max(res, sum);
        }
        return res;
    }

[SerenaZZZZZ]

Prefix sum相减：

class Solution {
    public int maxSubArray(int[] nums) {
        int minSum = Integer.MAX_VALUE;
        int sum = 0;
        int result = Integer.MIN_VALUE;
        for (int num: nums){
            minSum = Math.min(sum, minSum);
            sum+=num;
            result = Math.max(sum-minSum, result);
        }
        return result;
    }
}