最大子数组（有限制）

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

我们的普通做法有动态规划，我们设置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 = -infmin_pre_sum = pre_sum = 0for 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 longint 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;
}