题目链接

算法竞赛进阶指南-49.最大子序和

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \le n,m \le 300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

Method : 单调队列优化DP

i - dque.front() + 1 > m + 1，这里怎么理解？

因为对于前缀和数组来说：$s[r] - s[l - 1]$是算$arr[r] \sim arr[l]$的前缀和，
所以当原数组的滑动窗口长度为$m$时，前缀和数组的滑动窗口长度应为$m + 1$。

#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3e5 + 7;
const int INF = 0x3f3f3f3f;

int n, m;
vector<int> arr(N, 0);
vector<LL> sum(N, 0);

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    
    LL res = -INF;
    deque<int> Q;
    Q.push_back(0); // 插入sum[0]
    for (int i = 1; i <= n; i ++) {
        while (!Q.empty() && i - Q.front() + 1 > m + 1) {
            Q.pop_front();
        }
        
        res = max(res, sum[i] - sum[Q.front()]);
        
        while(!Q.empty() && sum[Q.back()] >= sum[i]) {
            Q.pop_back();
        }
        Q.push_back(i);
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n)}$， 对于数组中的每个元素，其最多只进出队列一次。

• 空间复杂度：${O(N)}$。