求最大连续和的几种方法

本文内容参考《算法竞赛入门经典第2版》220~223页
Q：给出一个长度为 n n n的序列 A 1 , A 2 , A 3 , ⋯   , A n A_{1},A_{2},A_{3},\cdots,A_{n} A1​,A2​,A3​,⋯,An​，求最大连续和。换句话说，要求找到 1 ≤ i ≤ j ≤ n 1\leq i\leq j \leq n 1≤i≤j≤n，使得 A i + A i + 1 + ⋯ + A j A_{i}+A_{i+1}+\cdots+A_{j} Ai​+Ai+1​+⋯+Aj​尽量大。
方法一：
暴力枚举，时间复杂度 O ( n 3 ) O(n^{3}) O(n3)

ans=A[1];//所求的最大连续和 
for(int i=1;i<=n;i++){
	for(int j=i;j<=n;j++){//枚举区间[i,j] 
		int sum=0;
		for(int k=i;k<=j;k++){//对区间[i,j]内的所有数求和 
			sum+=A[k];
		}
		ans=max(sum,ans);//取最大值 
	}
}

方法二：
利用前缀和，时间复杂度 O ( n 2 ) O(n^{2}) O(n2)

s[0]=0;
for(int i=1;i<=n;i++){//提前求前缀和（s[i]表示从A[i]数组从1到i的所有数之和），降低时间复杂度 
	s[i]=s[i-1]+A[i];
}
ans=s[0];
for(int i=1;i<=n;i++){
	for(int j=i;j<=n;j++){
		ans=max(ans,s[j]-s[i-1]);
	}
}

方法三：
分治法，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

int maxSum(int*A,int x,int y){//返回数组在左闭右开区间[x,y)中的最大连续和 
	if(y-x==1){
		return A[x];
	}
	int m=x+(y-x)/2;//划分成[x,m)和[m,y) 
	int maxs=max(maxSum(A,x,m),maxSum(A,m,y));
	int v,L,R;
	v=0;
	L=A[m-1];
	for(int i=m-1;i>=x;i--){//从分界点往左的最大连续和 
		L=max(L,v+=A[i]);
	}
	v=0;
	R=A[m];
	for(int i=m;i<y;i++){//从分界点往右的最大连续和 
		R=max(R,v+=A[i]);
	}
	return max(maxs,L+R);//子问题的解与L和R比较 
}