【最大子段和问题：不定长、定长、有长度上界】

题目

思考

我由这道题想起了一系列问题：

最大连续子段和        贪心 

最大连续子段和，但是区间长度为m        前缀和 

最大连续子段和，但是区间长度小于等于m        我的思考是从贪心上面改 

错误代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5+10;
LL a[N]; 
int main()
{
    int n, m, cnt = 0;
    cin >> n >> m;
    LL ans = -1e9, sum = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i], cnt++;
        if(sum > ans) ans = sum;
        if(sum < 0) sum = 0, cnt = 0;
        if(cnt >= m)
        {
            sum -= a[i-m+1];
        }
    }
    
    cout << ans;
    
    return 0;
}

正确代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N], s[N];
int ms[N], h = 1, t = 0;

int main() {
    
    int n, m;
    cin >> n >> m;
    int ans = INT_MIN;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
        
        int j = i-1; //j滞后i 1，因为s[i]不应该进入s[ms[h]]的最小值备选。对于每个s[i], 大小为m的范围指的是[i-m,i-1] = [j-m+1, j]
        while(h <= t && s[j] <= s[ms[t]]) t--; //队尾出
        ms[++t] = j; //队尾进
        if(ms[h] < j - m + 1) h++; //队头出
        ans = max(ans, s[i] - s[ms[h]]);
    }

    cout << ans;
    return 0;
}

感悟

正确代码将前缀和+二维搜索边界的问题转化为了——前缀和+单调队列的问题：

最大子段和 = max( s[ i ] - s[ j ] ) （s[ j ] 为 [ j-m+1, j ]， j = i-1范围内的最小值）

难点在于单调队列覆盖的范围都会进入最值考虑，而对于每个s[i]，s[i]是不进入最值考虑的（子段至少有一个数），因此i 要 比 j 大 1，i 参与最终前缀和计算， j 参与 单调队列的维护。