算法分析

单调队列

滑动窗口大小是k + 1

等价于在长度是k + 1的情况下，至少有一个是不选的，求出总和sum，算出损失的最小效率res，则sum - res即答案所求

以i结尾的f[i]，滑动窗口的区间是[i - k - 1,i - 1]，单调队列维护的是该区间的最小值，由于滑动窗口不包含i，因此f[i]需要在while上方进行更新

异曲同工的题目 LeetCode 1425. 带限制的子序列和

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int n,k;
    static int[] a = new int[N];
    static int[] q = new int[N];
    static long[] f = new long[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        long sum = 0;
        for(int i = 1;i <= n;i ++) 
        {
            a[i] = scan.nextInt();
            sum += a[i];
        }
        int hh = 0,tt = -1;
        long res = Long.MAX_VALUE;
        for(int i = 0;i <= n;i ++)
        {
            if(hh <= tt && q[hh] < i - k - 1) hh ++;
            if(hh <= tt) f[i] = f[q[hh]] + a[i];//观察第一项，是否需要第0项更新它，若需要将0入队
            while(hh <= tt && f[q[tt]] >= f[i]) tt --;
            q[++ tt] = i;

            if(i >= n - k) res = Math.min(res, f[i]);
        }
        System.out.println(sum - res);
    }
}