题目描述：

N个数围成一圈，要求从中选择若干个连续的数（注意每个数最多只能选一次）加起来，问能形成的最大的和。

输入描述：

第一行输入N，表示数字的个数，第二行输入这N个数字。

输出描述

输出最大和。

样例输入： 8 2 -4 6 -1 -4 8 -1 3

样例输出： 14

数据说明：

40% 1<=N<=300

60% 1<=N<=2000

100% 1<= N<=100000,答案在long long范围内。每个数的范围【-1000,1000】

本人代码（求调）

法一

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,a[(2*N)],dp[N],res=INT_MIN;
int MaxSum(int st,int ed){
    for(int i=1;i<2*n;i++)dp[i]=0;
    for(int i=st;i<=ed;i++){
        dp[i]=max(a[i],dp[i-1]+a[i]);
    }return dp[ed];
}
signed main(void){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n+1;i<2*n;i++){
        a[i]=a[i-n];
    }
    //for(int i=1;i<2*n;i++)cout<<a[i]<<' ';
    for(int i=1;i<=n;i++){
        int Sum=MaxSum(i,(i+n-1));
        //cout<<Sum<<' ';
        res=max(res,Sum);
    }cout<<res<<endl;
    exit(0);
}

法二

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;  
int a[N],n,s;  
int ans,ansmx,ansmi,mx,mi;  
signed main(void){  
    cin>>n;
    for(int i=1;i<=n;i++){  
        cin>>a[i];
        s+=a[i];  
    }  
    for(int i=1;i<=n;i++){  
        mx+=a[i],mi+=a[i];  
        if(mx>ansmx)ansmx=mx; 
        else if(mx<0)mx=0;
        if(mi<ansmi)ansmi=mi;
        else if(mi>0)mi=0;  
    }
    if(s-ansmi>ansmx)ans=s-ansmi;  
    else ans=ansmx;  
    cout<<max(signed(ans),signed(0))<<endl;
    exit(0);
}