51nod 循环数组最大子段和（动态规划）

循环数组最大子段和

输入

第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N+1行：N个整数 (-10^9 <= S[i] <= 10^9)

输出

 

输出循环数组的最大子段和。

 

输入示例

6
-2
11
-4
13
-5
-2

输出示例

20

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

不同语言如何处理输入输出，请查看下面的语言说明。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std ;
ll n,m,a[50005],dp[50005];ll b[505];
int main()
{
    cin>>n;ll sum=0,ans=inf;
    for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
    ll maxn=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+a[i],a[i]);
        ans=min(ans,dp[i]);
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1]+a[i],a[i]);
        maxn=max(maxn,dp[i]);
    }

    cout<<max(sum-ans,maxn)<<endl;
    return 0 ;
}