135 最大子序和（单调队列优化）

谁践踏了优雅 2022-08-28 07:48 133阅读 0赞

**1. 问题描述：**

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

**输入格式**

第一行输入两个整数 n,m。第二行输入 n 个数，代表长度为 n 的整数序列。同一行数之间用空格隔开。

**输出格式**

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

**数据范围**

1 ≤ n，m ≤ 300000

**输入样例：**

6 4  
1 -3 5 1 -2 3

**输出样例：**

7  
来源：[https://www.acwing.com/problem/content/description/137/][https_www.acwing.com_problem_content_description_137]

**2. 思路分析：**

分析题目可以知道我们需要求解一段长度小于等于m的区间和，并且这一段区间在所有长度小于等于m的区间中的区间和是最大的，所以这是一个最优化的问题，我们可以枚举以i为右端点，在左边找一个长度小于等于m的左端点使得区间和是最大的，枚举所有的左端点那么一定可以找到一个长度小于等于m的区间和是最大的，在枚举右端点的过程中其实是维护一个长度小于等于m的区间所以可以相当使用**单调队列**来优化（本质上是求解长度的m的滑动窗口的最值问题==>单调队列优化），在队列中维护一个单调递增的队列即可，可以先预处理前缀和然后在枚举右端点的时候维护最小的前缀和信息即可，队头元素就是区间和最小的位置。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_12_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == "__main__":
         n, m = map(int, input().split())
         w = list(map(int, input().split()))
         s = [0]
         # 预处理前缀和
         for i in range(1, n + 1):
              s.append(s[-1] + w[i - 1])
         q = [0] * (n + 1)
         # 一开始的时候s[0]为队列中的一个元素所以tt = 0
         hh, tt = 0, 0
         res = -10 ** 9
         for i in range(1, n + 1):
              # 不包含第i个位置(通过画图来确定边界)
              if hh <= tt and q[hh] < i - m: hh += 1
              # 更新答案: 当前位置的前缀和减去最小的前缀和那么得到的就是以当前位置结尾的前缀和的最大值
              res = max(res, s[i] - s[q[hh]])
              # 单调队列维护窗口长度小于等于m的最小前缀和的位置
              while hh <= tt and s[q[tt]] >= s[i]: tt -= 1
              tt += 1
              q[tt] = i
         print(res)

[https_www.acwing.com_problem_content_description_137]: https://www.acwing.com/problem/content/description/137/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ee4675118d924fbc855e4b9b1a59f0e5.png