题解 | #最美数字花环#

一道动态规划求最大子序和的问题，需要知道的是，这里是环，我们需要将环展开成线处理，每一次找最大的子序和，然后把它拿走（变为0）

#include<bits/stdc++.h>
using namespace std;
int n;
const int M=2e5+5;
int dp[M<<1];
int a[M<<1];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>dp[i];
		a[i]=dp[i];
	} 
	int cn=1;
	for(int i=n+1;i<=2*n;i++){
		dp[i]=dp[cn];
		a[i]=a[cn++];
	}
	int st=1,en=1,p=1;
	int maxn=dp[1];
	for(int i=2;i<=n;i++){
		if(dp[i-1]+dp[i]>=dp[i])
			dp[i]=dp[i-1]+dp[i];
		else p=i;
		if(dp[i]>maxn){
			maxn=dp[i];
			st=p; en=i;
		}
	}
	for(int i=st;i<=en;i++){
		a[i]=0;
	}
	for(int i=st+n;i<=en+n;i++){
		a[i]=0;
	}
////	for(int i=1;i<=2*n;i++){
//		cout<<a[i]<<" ";
//	}
//	cout<<endl;
//	cout<<st<<" "<<en<<endl;
	int maxn1=a[1];
	for(int i=2;i<=2*n;i++){
		if(a[i-1]+a[i]>=a[i])
			a[i]=a[i-1]+a[i];
		else p=i;
		if(a[i]>maxn1){
			maxn1=a[i];
		}
	}
//	cout<<maxn<<" "<<maxn1<<endl;
	cout<<maxn+maxn1<<endl;
}