动态规划设计：最大子数组 :: 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];
}

[yangyangDeveloper]

dp[i] = max(nums[i], dp[i - 1] + nums[i])

[shiboys]

你这个回复，初中水平都不到。Math.max的含义不会的话，可以去查查 JDK 呀

[super468]

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

[ElandWoo]

这是不是一种贪心思想。

[morganwu277]

第一种 算是贪心算法，当 windowSum < 0 的时候，这部分区间，不值得被使用，需要被丢弃，所以需要一直left++，直到 windowSum >=0 则right又可以继续往前跑了

[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;
	}
}

[lihuagang03]

打卡，感谢！

[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了？求解，我不知道是哪里看错了

[Demg777]

你没有错，最后dp[i]就是7，你应该好好看看dp的定义

[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;
    }
};

[listedH]

这个应该是最简单的写法了

[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;
    }
}

[yonggui-yan]

打卡打卡

滑动窗口不可以
dp[i]是nums[i]结尾的最大子数和
前缀和也可求解

[hurace]

文中的滑动窗口写法有误，不符合 窗口内元素之和大于等于 0 时扩大窗口，在窗口内元素之和小于 0 时缩小窗口，在每次移动窗口时更新答案

int maxSubArray(int* nums, int numsSize)
{
    int l = 0, r = 0;
    int winSum = 0, maxSum = -INT_MAX;
    while(r < numsSize) {
        if (winSum >= 0) {
            winSum += nums[r];
            r++;
        }

        maxSum = maxSum > winSum ? maxSum : winSum;

        if (winSum < 0) {
            winSum -= nums[l];
            l++;
        }
    }
    
    return maxSum;
}

[morganwu277]

既然这么咬文嚼字，那么我也来一个，针对你的答案的。😁
在每次移动窗口时更新答案 说法不精确，因为你在 winSum < 0 里面进行了 left++ 移动了窗口，但是你并未更新答案。

好吧，我只是觉得这个回复无聊。

[bruceeewong]

打卡，多种解题思路，学习了！

[biezhiwai]

int maxSubArray(vector& nums) {
for(int i = 1; i < nums.size(); i++){
nums[i] = max(nums[i], nums[i - 1] + nums[i]);
}
return *max_element(nums.begin(),nums.end());
}

[linhr11]

int left = 0;
int right = 0;
int max = nums[left];
int stage = nums[left];

    for (right = 1; right < nums.length ; right++) {
        if (stage + nums[right] <= nums[right] ){
            stage = nums[right];
            max = Math.max(max,stage);
        }else{
            stage = stage+nums[right];
            max = Math.max(max,stage);
        }

    }

    return max;

[CarlLy7]

打卡！！希望东哥这个网站能够一直维护啊，太宝藏了

[chiao666]

滑动窗口这个好巧妙，说实话还有几分迷糊，每当窗口里数字和小于0的时候，窗口不断缩小，左右指针重合，窗口变为0（想几种情况，应该是一定会窗口变为0），再开始扩大窗口，所以不会漏掉正数开头的情况