题目: 135. 最大子序和
输入一个长度为
n
的整数序列,从中找出一段长度不超过m
的连续子序列,使得子序列中所有数的和最大。
注意: 子序列的长度至少是1。
输入格式
第一行输入两个整数n
,m
。
第二行输入n
个数,代表长度为n
的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
$1≤n,m≤300000$
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
算法
不管怎样,第一反应就是前缀和。否则时间复杂度肯定太高。在把A
转换成了前缀和数组S
了之后,问题于是就变成了:
对于一个长度为n的序列
S
,从中找到一对数i
和j
满足0<j-i<=m
使得S[j]-S[i]
的值最大化。
算法1
(暴力枚举) 时间复杂度为$O(n^2)$
直接穷举所有可能的数对,算出他们的值,取最大值。
算法2
(单调队列) 时间复杂度为$O(n)$
注意到,如果i<j
并且S[i]>=S[j]
的话,如果k>j
并且要算出以S[k]
为第二个数的数对的最大值,那么我们是不可能取S[i]
的,因为S[j]
更小,能形成的差值更大。单调队列呼之欲出。所以每当窗口向右滑动,加入一个新的数x
的时候,我们可以把之前的单调队列里面的所有>=x
的数都移除了,那么确保加入了新的数的队列还是单调的。
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll n, m, S[N], q[N], hh, tt;
int main() {
cin>>n>>m;
for (int i=1; i<=n; i++) {
cin>>S[i];
S[i]+=S[i-1];
}
ll res=INT_MIN;
for (int i=1; i<=n; i++) {
if (hh<tt && q[hh]<i-m) hh++; // 确保还剩下起码一个数字,所以不是hh<=tt
res=max(res, S[i]-S[q[hh]]);
while (hh<=tt && S[q[tt]]>=S[i]) tt--;
q[++tt]=i;
}
cout<<res;
}