本文主要是介绍rqnoj-208-奥运火炬到厦门-dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题目是把一个连续的串看成一个环。
那么除了原始的求最大字段和外。
还存在一种情况是前面的连续最大值，加上后面的连续最大值。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[2000002];
int st[1000010];
int ed[1000010];
int main()
{int n,i;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);a[i+n]=a[i];}int maxx;maxx=-999999;int ans;ans=0;// int top=0;//st=0;for(i=0;i<n;i++){ans+=a[i];maxx=max(ans,maxx);if(i==0)st[i]=a[i];else st[i]=st[i-1]+a[i];if(ans<0){ans=0;}}ans=0;for(i=n-1;i>=0;i--){ed[i]=ed[i+1]+a[i];}for(i=1;i<n;i++){st[i]=max(st[i-1],st[i]);}for(i=n-1;i>=0;i--)ed[i]=max(ed[i+1],ed[i]);for(i=0;i<n;i++){// cout<<st[i]<<" "<<ed[i+1]<<endl;maxx=max(maxx,st[i]+ed[i+1]);}cout<<maxx<<endl;return 0;
}
这篇关于rqnoj-208-奥运火炬到厦门-dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
