最大子数组（有限制）

前言：最大子数组问题之前做过，但是一时脑抽没有记起来

我们的普通做法有动态规划，我们设置dp[ i ] 为以 i 结尾的最优解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int now = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (now>= 0) {
                now = now + nums[i];
            }
            else now = nums[i];
            ans = max(ans, now);
        }
        return ans;
    }
};

我们还可以用前缀和的思路去做

这个思路特别妙，我们只要用当前的前缀和减去之前最小的前缀和，那么就可以得到以 i 结尾的最优解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        min_pre_sum = pre_sum = 0
        for x in nums:
            pre_sum += x  # 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值
        return ans

我们再来看一个进阶版的题目
题目地址

这个我们加入了限制 w ，除外其实就是一个最大子数组

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n,wei;
const int N = (int) 1e6+10;
int w[N],d[N];
int sum[N];

signed main(){
	cin >> n >> wei;
	for(int i=1;i<=n;i++){
		cin >> w[i];
	}
	for(int i=1;i<=n;i++){
		cin >> d[i];
		sum[i] = sum[i-1] + d[i];
	}
	int ans = LLONG_MIN;
	int now = 0;
	set<int> b;
	int l = 1;
	for(int i=1;i<=n;i++){
		now += w[i];
		while(now>wei){
			b.insert(sum[l-1]);
			now -= w[l++];
		}
		if(!b.empty()) ans = max(ans,sum[i]-*b.begin());
	}
	cout << ans << endl;
	return 0;
}