单调队列 + 前缀和：连续子序列的最大和

文章目录

单调队列 + 前缀和：连续子序列的最大和

单调队列

单调队列能在O(N)的时间内方便地维护一个长度为n的序列中,每个长度为m的区间的区间最值。单调队列是一个双端队列，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。单调递增队列内部元素始终为单调递增。同理单调递减队列内部始终为单调递减。而我们对单调队列进行的所有操作就是为了维护上述单调性质。
我们通过一个例子理解单调队列的运作方式：

队列为单调递增队列时，若当前元素大于队尾元素，则当前元素入队，队列保持单调递增。若当前元素小于队尾元素，则我们需要将队尾元素不断出队，直到新的队尾元素小于当前元素，再将当前元素入队，这样才能保证队列单调递增。
若当前遍历的是第i位元素，我们需要维护长度为m的子区间的最值，即队列中的元素必须在[i – m + 1,i]范围内，队首元素一定是队列中最早入队的元素，若队首元素不在此范围内，则将队首元素出队。
我们通过队尾的出入队来维持队列的单调性质，用队首的出队来维持队列中元素都处在某个子区间内，由于队列的单调性，队首元素一定是该子区间内的最小或最大值。

问题：

思路：

题目要我们在一个序列A中找到长度不超过m子区间，使这个子区间的和最大。对于求子区间的和的问题，我们可以使用前缀和数组pre[]，[i,j]子区间的和即为pre[j] - pre[i - 1]。若我们确定子区间的终点j，长度不超过m的子区间即为[j - m + 1,j] ~ [j,j]。而这些子区间中的最大和为多少呢，通过子区间和的公式可以看出，这些子区间中的最大和为pre[j] - min(pre[j - m] ~ pre[j])，则我们需要知道pre[j - m] ~ pre[j]中的最小值，此时单调队列就登场了，即我们需要维护一个保存长度为m + 1的区间内最小值的单调队列。
根据上述方法，我们可以求得确定右端点的子区间和的最大值，枚举每个元素为子区间的右端点，不断更新最大值即可

需注意的点：
java中ArrayDeque和LinkedList类实现了双端队列Deque接口，分别提供了双端队列的数组和链表实现。Deque接口的几个常用的方法如下：

方法	说明
void addFirst(E element)	将元素添加到队首
void addLast(E element)	将元素添加到队尾
E pollFirst()	队列不为空，删除并返回队头元素
E pollLast()	队列不为空，删除并返回队尾元素
E getFirst()	队列不为空，返回队头元素
E getLast()	队列不为空，返回队尾元素

代码：

import java.util.*;

public class Main {
    static ArrayDeque<Integer> q = new ArrayDeque<>();
    static long[] pre = new long[300002];
    public static void main(String[] args) {
        int n, m, i;
        long ans = 0, num;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (i = 1;i <= n;i++) {
            num = scanner.nextLong();
            pre[i] = pre[i - 1] + num;
            while (!q.isEmpty() && pre[q.getLast()] > pre[i]) {
                q.pollLast();
            }
            q.addLast(i);
            if (q.getFirst() < i - m) {
                q.pollFirst();
            }
            if (pre[i] - pre[q.getFirst()] > ans) {
                ans = pre[i] - pre[q.getFirst()];
            }
        }
        System.out.println(ans);
    }
}