算法分析

单调队列

• 1、需要求某一个区间的连续子段和，因此需要用到前缀和s[]
• 2、对于任意的s[i],求以i结尾的区间长度不超过m的最大连续和，等价于求s[i] - s[j - 1]的最大值，其中i - m <= j - 1 <= i - 1，即要求s[j - 1]的最小值，因此滑动窗口的区间是[i - m,i - 1]，单调队列维护的是该区间的最小值，由于滑动窗口不包含i，因此res需要在while上方进行更新，

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 300010;
    static int[] s = new int[N];
    static int[] q = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1;i <= n;i ++)
        {
            s[i] = scan.nextInt();
            s[i] += s[i - 1];
        }
        int hh = 0, tt = 0;
        int res = -0x3f3f3f3f;
        for(int i = 1;i <= n;i ++)
        {
            if(hh <= tt && q[hh] < i - m) hh ++;
            if(hh <= tt) res = Math.max(res,s[i] - s[q[hh]]);
            while(hh <= tt && s[q[tt]] >= s[i]) tt--;
            q[ ++ tt] = i;

        }
        System.out.println(res);
    }
}

Java 代码（用小根堆实现）

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int N = 300010;
    static PriorityQueue<Pair> q = new PriorityQueue<Pair>((x,y) -> x.val - y.val);
    static int[] s = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1;i <= n;i ++)
        {
            s[i] = scan.nextInt();
            s[i] += s[i - 1];
        }

        int res = -0x3f3f3f3f;
        for(int i = 1;i <= n;i ++)
        {
            int t = s[i] - s[i - 1];
            while(!q.isEmpty() && i - m > q.peek().idx) q.poll();
            if(!q.isEmpty()) t = Math.max(t, s[i] - q.peek().val);
            res = Math.max(res,t);
            q.add(new Pair(s[i],i));
        }
        System.out.println(res);
    }

}
class Pair
{
    int val,idx;
    Pair(int val,int idx)
    {
        this.val = val;
        this.idx = idx;
    }
}