$$\color{Red}{最大子序和 【单调队列优化（区间判断和之前不同的解析）】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 1。

输入格式

第一行输入两个整数 n, m。

第二行输入 n 个数，代表长度为 n 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

1 ≤ n, m ≤ 300000

保证所有输入和最终结果都在 int 范围内。

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

思考

我的滑动窗口题解 这道题就是单调队列的思想

可以点入我的题解，看一下基本的单调队列做法的思想是什么。

这道题我们看到求连续的子序列的和，首先第一直觉肯定能想到我们肯定要使用前缀和，方便我们随时计算。

这里我们想要求一个最大的序列和，从暴力的角度看，我们可以枚举所有的子序列，以 O(2 ^ n)的时间复杂度，找到最大的那个。

可惜这里会超时，我们应该想一个优化的方式。

单调队列优化

这里我们从集合角度，使用动态规划进行思考。

我们设状态方程 f[i] ，代表所有以 i 位置元素为结尾，而区间长度小于等于 m的子序列的集合。其存储的属性为，这些子序列集合中那个子序列和的最大的序列，存储最大值。

此时我们显然从暴力角度思考，是从 i - m -> i - 1 下标位置的点作为起点(这里假设用索引 j遍历)，依次计算 s[i] - s[j-1]的最大值。就是我们最开始的暴力思路。

那么如何进行单调队列优化？

我们终点固定的情况下，显然我们只想找到那个最小的 ‘s[j-1]’，这样相减得到的序列和才是最大的，那么类似滑动窗口这道题，当窗口移动的情况下，会让我们整个区间少一个元素，再添加一个新元素，如果添加的元素值小于等于此前区间的最小值，那么我们永远都不会相减的时候用到它（先进先出）。

那么我们只需要维护一个单调队列，保存一个递增的序列，每次使用队头的最小元素进行计算答案，和之前滑动窗口几乎相同的做法。

相信之前做滑动窗口这道题，再做这道题，最开始的窗口移动判断用的下标一会需要 + 1， 一会不用，会产生一个大大的疑问：

子序列的长度是点的个数还是边的个数？

子序列的长度通常指包含的元素个数。

之前的滑动窗口的大小，其实和子序列的长度表示的含义是一致的。

它进行位移判断使用的是 if (hh <= tt && q[hh] < i - k + 1) hh ++;

这里 i - k + 1的值代表的是滑动窗口的左端点应该在的位置，当此时这个位置的索引位置已经超越我们单调队列的最左边的元素的下标，代表这个元素已经不在我们维护的范围内了，需要把它从队列移除。

而这道题的位移判断是 if (hh <= tt && q[hh] < i - k) hh ++ ;

为什么和我们的之前的判断少了一个 + 1 ，应该 + 1 才是算出当前维护区间的左端点下标啊，这么不是维护了一个 k + 1 的区间？

但是我们要思考，我们计算序列和，用前缀和的计算是： s[r] - s[l - 1]，才是 序列 l -> r这段的长度，所以我们维护的的单调队列里面相当于s[l-1]的值,故维护的区间也应该向左多一格

之前的滑动窗口我们明明是从空队列开始枚举的，这里为什么非要加入一个元素0？不加还AC不了

因为插入了一个前缀和标杆0，不加0的话，如果第一个元素能取到的情况下，每次都取不到，因为减的是s[l - 1]

换句话说，我们维护的区间应该是 k + 1 长度，的s[l - 1]，需要给第一个元素加入的情况，预处理一个 0

可以手动模拟一下，如果不加的花，答案如果是覆盖了第一个点的区间，那么每次后面的进行相减用到的s[q[hh]]，就把第一个元素的值都减掉了。

java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int n, m, N = 300010;
    static int [] s = new int[N];
    static int [] q = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String [] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        String [] s2 = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + Integer.parseInt(s2[i - 1]);

        long res =(long) -1e18;
        // 这里默认队列保存了一个元素 q[0] = 0
        int hh = 0, tt = 0;
        for (int i = 1; i <= n; i++) {
            if (hh <= tt && i - m > q[hh]) hh++;
            res = Math.max(res, s[i] - s[q[hh]]);
            while (hh <= tt && s[i] <= s[q[tt]]) tt --;
            q[++tt] = i;
        }
        System.out.println(res);
    }
}