올림픽 성화 하문-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;
}