输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。 注意： 子序列的长度至少是1。 输入格式 第一行输入两个整数n,m。 第二行输入n个数，代表长度为n的整数序列。 同一行数之间用空格隔开。 输出格式 输出一个整数，代表该序列的最大子序和。 数据范围 1≤n,m≤3000001≤n,m≤300000 输入样例： 6 4 1 -3 5 1 -2 3
输出样例： 7
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 300010, INF = 1e9; int n, m; int s[N]; int q[N]; int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++){ scanf("%d", &s[i]); s[i] += s[i - 1]; } int res = -INF; int hh = 0, tt = 0; for (int i = 1; i <= n; i ++){ if (q[hh] < i - m) hh ++; res = max(res, s[i] - s[q[hh]]); while(hh <= tt && s[q[tt]] >= s[i]) tt --; q[++ tt] = i; } cout << res << endl; return 0; }