[前缀和, 单调队列]最大子序和
135. 最大子序和 - AcWing题库
输入一个长度为 nnn 的整数序列,从中找出一段长度不超过 mmm 的连续子序列,使得子序列中所有数的和最大.
注意: 子序列的长度至少是 111 .
第一行输入两个整数 n,mn,mn,m .
第二行输入 nnn 个数,代表长度为 nnn 的整数序列.
同一行数之间用空格隔开.
输出一个整数,代表该序列的最大子序和.
1≤n,m≤3000001 \le n,m \le 3000001≤n,m≤300000
1 -3 5 1 -2 3
方法一:前缀和 单调队列
看到求连续区间之和的问题,首先想到用前缀和进行优化,然后就是枚举区间的问题:暴力