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/
2. 思路分析：
分析题目可以知道我们需要求解一段长度小于等于m的区间和，并且这一段区间在所有长度小于等于m的区间中的区间和是最大的，所以这是一个最优化的问题，我们可以枚举以i为右端点，在左边找一个长度小于等于m的左端点使得区间和是最大的，枚举所有的左端点那么一定可以找到一个长度小于等于m的区间和是最大的，在枚举右端点的过程中其实是维护一个长度小于等于m的区间所以可以相当使用单调队列来优化，在队列中维护一个单调递增的队列即可，可以先预处理前缀和然后在枚举右端点的时候维护最小的前缀和信息即可，队头元素就是区间和最小的位置。
3. 代码如下：
if __name__ == "__main__":
n, m = map(int, input().split())
a = list(map(int, input().split()))
s = [0]
# 预处理前缀和
for i in range(len(a)):
s.append(s[-1] + a[i])
# hh为队列头指针位置, tt为队列尾指针位置
hh, tt = 0, 0
q = [0] * n
res = -10 ** 9
for i in range(n):
# 窗口的长度大于了m那么需要将当前的头指针往后移动
if q[hh] <= i - m: hh += 1
res = max(res, s[i + 1] - s[q[hh]])
while hh <= tt and s[i] <= s[q[tt]]: tt -= 1
tt += 1
# 单调队列存储元素的下标
q[tt] = i
print(res)
