题目描述
输入一个长度为 n 的整数序列,从中找出一段长度不超过 m 的连续子序列,使得子序列中所有数的和最大。
注意: 子序列的长度至少是 1。
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数,代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数,代表该序列的最大子序和。
数据范围
1≤n,m≤300000
样例
输入样例:
6 4
1 -3 5 1 -2 3
输出样例:
7
算法1
(动态规划)
枚举以每一个数结尾的连续子序列。
对于当前的值ai,如果以ai-1结尾的子序列的和为>=0,那就把ai加入到以ai-1结尾的子序列中,此时当前的子序列结尾变成了以ai结尾的子序列。让后更新一下当前序列的子序和与最大子序和。
对于当前的值ai,如果以ai-1结尾的子序列的和为<0,那就不要前面子序列了,以ai开始重新规划子序列。
因为此题还要求了子序列的长度为m,因此我们在累加当前的子序列时,还要统计当前子序列的长度。如果子序列达到了最大长度,那要从这一段子序列的开头加+1处重新开始累加新的子序列。
时间复杂度
对于当前的元素ai,要不以它最为新的子序列的开始,要么加入到上一子序列中。这些操作都可在O(1)的时间复杂度内完成。
我们要从头遍历完所有元素,总的时间复杂的是O(N),但是运行时间要比双端对列的时间长,因为有一些元素会被频繁使用到多次,而双端对列保证每一个元素至多进队出队一次。
C++ 代码
#include<iostream>
#include<limits.h>
using namespace std;
const int N=300005;
int numbers[N];
int pre_sum[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&numbers[i]);
pre_sum[1]=numbers[1];//从第一个元素算起
int max_sum=pre_sum[1],cur_len=1;
int start=1;
for(int i=2;i<=n;++i){
if(pre_sum[i-1]<0) {
pre_sum[i]=numbers[i];
start=i;
cur_len=1;
max_sum=max(max_sum,pre_sum[i]);
if(cur_len==m) pre_sum[i]=-1;
}
else {
if(cur_len<m){
pre_sum[i]=pre_sum[i-1]+numbers[i];
max_sum=max(max_sum,pre_sum[i]);
cur_len++;
}
else {
++start;
i=start;
pre_sum[i]=numbers[i];
}
}
}
printf("%d",max_sum);
}
算法2
(双端队列)
求所有元素的前缀合。
枚举以i结尾并且长度为m的子序列的和,即sumi-sum(i-m)的前缀合。
因为对于对于这之中的m个元素,若sumk>sumj,且看k<j,那么对于sumj来说sumk是没用的,可以把sumk删掉。
基于这一思路,可以用一个队列保存以i结尾的前m-1个前缀合元素,队列中的元素满足严格单调递增。
对于以i结尾的子序列,因为队列中的元素满足严格单调递减,所以此段序列的最大值就是队尾元素减去对头元素。
处理完以i结尾的子序列以后,将队尾中大于等于i的前缀合都出队,然后让sumii加入到队列的末尾。即保持整个队列的单调性不变。
时间复杂度
每个元素之多出队一次入队一次,时间复杂度O(N)
参考文献
C++ 代码
#include<iostream>
#include<limits.h>
using namespace std;
const int N=300005;
int nums[N];
int sum[N];
int q[N],h,t;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&nums[i]);
sum[i]=sum[i-1]+nums[i];
}
q[t++]=0;
int ans=INT_MIN;
for(int i=1;i<=n;++i){
while(i-q[h]>m) h++;
ans=max(ans,sum[i]-sum[q[h]]);
while(sum[q[t-1]]>=sum[i]&&t>h) t--;
q[t++]=i;
}
printf("%d",ans);
}