算法题：最大子序和

问题描述

输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。 例如 1，-3,5,1，-2,3 当m=4时，S=5+1−2+3=7

当m=2或m=3时，S=5+1=6

输入格式

第一行两个数n,m（n,m≤300000）

第二行有n个数，要求在n个数找到最大子序和

输出格式

一个数，数出他们的最大子序和

样例

输入

6 4
1 -3 5 1 -2 3

输出

7

解决方案

思路

前缀和&&单调队列

代码

#include <iostream>
#include <queue>

using namespace std;

int n, m, t;
int sum[300005];

int main() {

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t);
        sum[i] = sum[i - 1] + t;
    }

    int result = -0x3c3c3c3c;
    deque<pair<int, int>> q;
    for (int i = 1; i <= n; ++i) {
        while (!q.empty() && i - q.front().first > m) q.pop_front();
        result = max(result, sum[i] - q.front().second);
        while (!q.empty() && sum[i] <= q.back().second) q.pop_back();
        q.push_back({i, sum[i]});
    }

    cout << result;
    return 0;
}