AcWing 135. 最大子序和

题目传送门

一、暴力+前缀和

• 需要求某一个区间的连续子段和，因此需要用到前缀和s[]。
• 区间必然有终点,每个结点都可以作为终点，所以可以通过枚举每个结点作为终点，找出所有的情况。
• 对于任意的s[i],求以i结尾的区间长度不超过m的最大连续和，等价于求s[i] - s[j - 1]的最大值，其中'i - m < = j - 1 < = i - 1'

#include 

using namespace std;
//Brute-force 暴力
const int N = 300010;
const int INF = 0x3f3f3f3f;
int s[N];
int res = -INF;
int n, m;

//TLE掉3个点
//通过了 11/14个数据
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
    //遍历每一个终点
    for (int i = 1; i <= n; i++)
        //从终点向前，找出所有区间在m之内的数字，通过前缀和计算出区间的累加和，保留最大值
        for (int j = i; j && j > i - m; j--)
            res = max(res, s[i] - s[j - 1]);

    cout << res << endl;
    return 0;
}

二、单调队列优化

因为当枚举每个结点i时，可以视为i是固定的，而j是在区间i - m + 1 <= j <= i 内滑动，所以s[i]是一个固定值，变化的其实是j,即要求s[j - 1]的最小值。滑动窗口的区间是[i - m,i - 1]，单调队列维护的是该区间的最小值，由于滑动窗口不包含i，因此res需要在while上方进行更新。

#include 

using namespace std;
const int N = 300010;
const int INF = 0x3f3f3f3f;
int n;      //n个数字
int m;      //连续长度为m
int q[N];   //单调队列，记录的是序号
int s[N];   //前缀和

int main() {
    //优化输入
    ios::sync_with_stdio(false);

    cin >> n >> m;
    //前缀和
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    //滑动窗口:i前面(不包括i)长度为m的窗口
    //单调队列一般将q中初始化一个0进去(tt=0)，防止q队列中没有数据，导致整体逻辑失败。
    int hh = 0, tt = 0;
    int res = -INF; //预求最大，先设最小
    for (int i = 1; i <= n; i++) { //遍历每一个结点
        if (q[hh] < i - m)hh++;    //如果队列头已经距离i结点大于m个长度，队列头结点需要出队列
        res = max(res, s[i] - s[q[hh]]);    //通过前缀和计算，获取此时区间和的值，试图更新最大值.其实是sum([队列头+1,i])
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;//单调队列，左侧最小
        q[++tt] = i;    //加入队列
    }
    //输出结果
    printf("%d", res);//是前缀和，就要小心会不会爆int,但此题n,m上限只有300000，即使是n*m也不会爆int,不用开long long
    return 0;
}