算法提高课汇总

算法思路

求区间和问题首先计算前缀和$s(i)$, 以快速计算某个区间和.

从集合角度考虑如何求最值问题.

• 集合划分: 一种划分方式是以区间右端点作为依据, 则集合被划分为$n$份.

• 集合计算: 对于右端点为$k$的区间, 所有区间和为$s(k) - s(k - j)$, 其中$j$表示区间长度,
  $1\le j\le min\lbrace k, m\rbrace$. 为求区间最大值, 由于$s(k)$固定, 我们需要在$s(k - 1)\sim s(k - min\lbrace k, m\rbrace)$
  — 即在固定区间内求最值, 可以用单调队列求解, 具体思路见 AcWing 154. 滑动窗口 .

代码实现 $O(n)$

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

using namespace std;

const int N = 3e5 + 10, INF = 1e9;

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 = -1;
    q[++ tt] = 0; //首先加入s(0) -- 区间长度至少为1
    for ( int i = 1; i <= n; i ++ )
    {
        if ( i - q[hh] > m )    hh ++ ; //这里考虑的是q[hh] ~ i - 1的长度
        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;
}