[C++知识库]最大子序和

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

题解

通过h，t和数字q[ ]，来记录m长度内的最小的数组。

每次用max函数来比较那个大那个小。

答案

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 300010, INF = 0x3f3f3f3f;

int n, m;
int s[N], 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;
? ? }

? ? printf("%d\n", res);

? ? return 0;
}