51nod 循环数组最大子段和

  http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

  对于普通的数组,只要求一次最大子段和即可。但是这题是可以循环的,所以要另外分析。

  1:最大的值在原数组中间部分。

  2:最大值是结尾部分和开头部分。(如果要循环,就是这种情况)

  对于1情况可以做一次最大子段和。而第二种情况出现时因为,中间部分很小,加了后最后的值会变小,所以不能加,也就是说中间部分的

值取反后,是最大的。这样就可以先进行对原数组的值取反,然后求一次最大子段和,那么求出来的就是原来负数最大的部分,然后只要这个值+

原数组的所有数值和,就是开头部分和结尾部分的值了。取1,2的最大值就是答案。

#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 99999999
#define mod 1000000007
#define ll __int64
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define key_value ch[ch[root][1]][0]
using namespace std;
const int MAXN = ;
ll b[MAXN],dp[MAXN];
ll getans(ll a[],int n)
{
ll ans = ;
memset(dp,,sizeof(dp));
for(int i=; i<=n; i++){
if(dp[i-] + a[i] < a[i]){
dp[i] = a[i];
}
else {
dp[i] = dp[i-] + a[i];
}
ans = max(ans,dp[i]);
}
return ans;
}
int main()
{
int n;
while(cin >>n)
{
ll sum = ;
for(int i=; i<=n; i++){
cin >>b[i];
sum += b[i];
}
ll ans = getans(b,n);
for(int i=; i<=n; i++){
b[i] = -b[i];
}
ans = max(ans,sum + getans(b,n));
cout<<ans<<endl;
}
}
上一篇:AVAssetReader+AVAssetReaderTrackOutput播放视频


下一篇:番外篇1:在Windows环境中安装JDK