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[],dp[];ll b[];

int main()

{

    cin>>n;ll sum=,ans=inf;

    for(int i=;i<=n;i++){cin>>a[i];sum+=a[i];}

    ll maxn=;

    for(int i=;i<=n;i++)

    {

        dp[i]=min(dp[i-]+a[i],a[i]);

        ans=min(ans,dp[i]);

    }

    memset(dp,,sizeof(dp));

    for(int i=;i<=n;i++)

    {

        dp[i]=max(dp[i-]+a[i],a[i]);

        maxn=max(maxn,dp[i]);

    }

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

    return  ;

}