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;  
}

补充：软件开发 , C++ ,