51nod 1050 循环数组最大子段和 (dp)

http://www.51nod.com/onlineJudge/questionCode.html#problemId=1050&noticeId=13385

参考:http://blog.csdn.net/acdreamers/article/details/38760805

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll; int n;
ll a[]; ll work()
{
ll temp=,m=;
for(int i=;i<n;i++)
{
temp+=a[i];
if(temp<) temp=;
if(m<temp) m=temp;
}
return m;
}
int main()
{
int t;
ll sum,sum1,sum2;
scanf("%d",&t);
while(t--)
{
sum=;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
sum1=work();
for(int i=;i<n;i++)
a[i]=-a[i];
sum2=work();
// printf("%lld %lld %lld\n",sum,sum1,sum2);
sum=max(sum+sum2,sum1);
printf("%lld\n",sum);
}
return ;
}
上一篇:Flink HA


下一篇:CentOS 6.0图解网络安装全过程