本文共 2485 字，大约阅读时间需要 8 分钟。

题目描述

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

注意： 子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n$ ,$m$。

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

输出格式

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

数据范围

$1$ $\le$ $n$ ,$m$ $\le$ $300000$

输入样例

6 4

1 -3 5 1 -2 3

输出样例

7

题解

算法1：暴力枚举 $O(nm)$

通过两层循环枚举每一个不超过$m$的连续子序列

code

#include
   
    using namespace std;const int N=3e5+10;int n,m,a[N],maxn=-1,sum=0;int main(){
   				cin>>n>>m;	for(int i=1;i<=n;i++) cin>>a[i]; 	for(int i=1;i<=n-m+1;i++) //i表示以i开头的子序列  	{
     		sum=0;//枚举每个子序列前将sum初始化   		for(int j=i;j<=i+m-1;j++) //j表示子序列的长度   		{
      			sum+=a[j]; 		 	maxn=max(sum,maxn);  		} 	} 	cout<
   

算法2：前缀和优化 $O(nm)$

利用前缀和解决算法1中的$sum$的累加过程

#include
   
    using namespace std;const int N=3e5+10;int n,m,a[N],s[N],maxn=-1,sum=0;int main(){
   		cin>>n>>m;	for(int i=1;i<=n;i++) cin>>a[i]; 	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//s[i]表示a[1]+a[2]+...+a[n]  	for(int i=1;i<=n;i++) 	{
     		int x=i-m;//x为与i距离为m的点的前一位，即最远的左端点的前一位  		if(x<0) x=0;//防止下标越界  		for(int j=x;j<=i-1;j++)//枚举左端点的前一位   			maxn=max(maxn,s[i]-s[j]); 	} 	cout<
   

算法3：优先队列优化 $O(N)$

假设$s$数组中的三个下标分别为 $i，j，k（k<j<i)$

根据算法2中的前缀和优化，在 $i$保持不变的情况下，$s[i]$也保持不变，序列的中所有数的累加和为$s[i]-s[left]$，所以$s[left]$越小，序列中的数字和就越大，也就更优。 那么如果$s[k]\ge s[j]$那$k$一定是一个无用的点，因为相比较而言，$k$的位置以及$s$数组中的值都不如$j$号点，所以$k$就没有任何价值 所以可以设计一个算法 用一个队列来模拟以下的操作，队列储存的是这个子序中每个元素的编号 从前向后遍历，如果$i$到队首的元素编号$q[head]$超过了$m$，就把队首往后推 如果我当前这个元素的值要比队尾的元素更优，即$s[i]<s[q[tail]]$（从前面的讲解可知，元素的价值取决于它的位置和$s$数组中的值，因为是从前向后遍历，所以当前位置一定比队列中任何一个数的位置更优，所以只需要比较$s$数组中的值）就将队尾的元素删去，并把这个元素塞到队尾 由此可知，当前维护的队列一定是一个具有单调性的（从队首到队尾的元素均从大到小或从小到大），因此称为单调队列 最后不断更新ans的值就可以啦

由于每个点都只会进出队列一次，所以时间复杂度就是$O(N)$

#include
   
    using namespace std;const int N=300010;int a[N],s[N],q[N],head=0,tail=0;int main(){
   	int ans=-1;	int n,m;	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)	{
   		scanf("%d",&a[i]);		s[i]=s[i-1]+a[i];//前缀和	}	for(int i=1;i<=n;i++)	{
   		if(i-q[head]>m) head++;//处理队首		//用if的原因是对于i来说，最多只可能把队首踹掉一次。		//其他大于i的点已经被i号点以前的点给踹掉了，也就是说被踹掉的队首一定是第i-m号点		while(s[i]<=s[q[tail]]&&head<=tail) tail--;//处理队尾		//用while的原因是队尾可能有多个大于等于s[i]的点，要将这些点都踹掉才可以		q[++tail]=i;//储存当前的点		ans=max(ans,s[i]-s[q[head]]);//更新答案			}	printf("%d",ans);	return 0;}