【HAUT OJ1282】ykc想吃好吃的

题目链接：http://218.28.220.249:50015/JudgeOnline/problem.php?id=1282

1282: ykc想吃好吃的

时间限制: 1 秒   内存限制: 128 MB

题目描述

一天，ykc在学校闲的无聊，于是决定上街买点吃的，ykc很懒，本来就不是很像逛街，于是找来了czl帮他买，这里应该有滑稽，而czl也不愿为ykc买东西吃，但是ykc很强势，非让他去买，呢没办法了，然而czl还有很多事要做，没呢么多时间帮ykc，而这条小吃街又很长，有n家店，n有50000这么大，并且这n家店的商品价值有所不同（要知道，商品的价值可能为负，哈哈，很神奇吧，但是czl肯定不会傻到赔钱，所以你懂的），哇，czl要疯了，他不想逛这么久啊，他还有个毛病，他只会连续的逛若干家店，并且由于这条街的店很多，所以肯定不会是一条直线，换句话说就是首尾相连，即第n家店和第一家店是连在一起的，然而ykc希望czl买的东西价值最大，不然就会不开心，于是他就把艰难的任务交给你了，他真的不想浪费时间，你能帮助他吗？

输入

第1行：小吃街的长度N（2 <= N <= 50000) 第2 - N+1行：N个整数，代表每个店的商品价值 (-10^9 <= S[i] <= 10^9)

输出

czl能买到的最大价值

样例输入

6 -2 11 -4 13 5 -2

样例输出

25

提示

水题一道

来源

题意：给定一个长度为50000的数组，求它的循环数组的最大子段和。

分析：本题与普通的最大子段和问题不同的是，最大子段和可以是首尾相接的情况，即可以循环。那么这个题目的最大子段和有两种情况 （1）正常数组中间的某一段和最大。这个可以通过普通的最大子段和问题求出。 （2）此数组首尾相接的某一段和最大。这种情况是由于数组中间某段和为负值，且绝对值很大导致的，那么我 们只需要把中间的和为负值且绝对值最大的这一段序列求出，用总的和减去它就行了。 即，先对原数组求最大子段和，得到ans1，然后把数组中所有元素符号取反，再求最大子段和，得到ans2， 原数组的所有元素和为ans，那么最终答案就是 max(ans1, ans + ans2)。

代码：

#include<iostream> using namespace std; typedef long long LL; LL arr[50003]; int main() { LL ans;//1~n总和 LL ans1;//普通的子列和 LL ans2;//（成环时）子列为负数时的和 LL n; while(cin>>n) { ans=ans1=ans2=0; LL MAX=0;//普通的子列最大和 LL MIN=0;//（成环时）子列为负数且绝对值最大时的和 for(LL i=0;i<n;i++) { cin>>arr[i]; ans+=arr[i]; } for(LL i=0;i<n;i++) { ans1+=arr[i]; ans2+=arr[i]; MAX=max(MAX,ans1); MIN=min(MIN,ans2); if(ans1<0) ans1=0; if(ans2>0) ans2=0; } cout<<max(ans-MIN,MAX)<<endl; } return 0; }