最大子序和

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

题解

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

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

答案

#include
#include
#include

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("%dn", res);

    return 0;
}