循环数组最大子段和

循环数组最大子段和

循环数组最大子段和
输入

第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 ;
}
04-25 04:18