算法思路

ys分析

    ys分析:从集合角度分析最优化问题.也就是在一个有限集中求最值时用集合划分元素.

    集合分类:(找不同点)
        以子序列的终点分类,可以将集合划分为n个不同终点的长度不超过m的子序列,这n个集合不重不漏.
        让每个子序列和最大,取其中最大值.
    集合最值:
        以a[k]作为结尾的子序列有m个, 快速求一个区间和可以用前缀和思想.
        令s[]为前缀和数组, 那么以a[k]结尾长度为j的子序列和为s[k] - s[k-j]
        求max(s[k] - s[k-j]), s[k]固定 --> 求min( s[k-j] ) k-m <= j < k
        一个区间的极值可以用单点队列优化.

时间复杂度

单调队列:$O(n)$

C++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;

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

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, tt = -1, hh = 0;
    q[ ++tt ] = s[0];
    for( int i = 1; i <= n; i++ )
    {
        if( q[hh] < i - m ) hh ++; //超出[i-m,i)
        res = max( res, s[i] - s[q[hh]] );
        while( hh <= tt && s[i] < s[q[tt]] )    tt -- ;
        q[ ++tt ] = i;
    }
    printf("%d\n",res);

    return 0;
}