假·最大子段和 (sdutoj 4359 首尾相连)(思维)

题目链接:http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2736/pid/4359

AC代码:

#include<iostream>

#include<cstring>

#include<iomanip>

#include<stdio.h>

#include<algorithm>

using namespace std;

# define inf 0x3f3f3f3f

# define ll long long

const int maxn = 200000+100;

int a[maxn];

int main(){

int T;

scanf("%d",&T);

while(T--){

int n;

scanf("%d",&n);

ll sum=0;

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

scanf("%d",&a[i]);

sum+=a[i];

}

ll tmp1=0,ans1=0,ans2=0;

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

tmp1+=a[i];

ans1=max(ans1,tmp1);

if(tmp1<0)tmp1=0;

}

tmp1=0;

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

tmp1+=(-a[i]);

ans2=max(ans2,tmp1);

if(tmp1<0)tmp1=0;

}

printf("%lld\n",max(sum+ans2,ans1));

}

return 0;

}