【多校连萌2】D题 ykc想吃好吃的【补题】【最大子段和变形题】

题目描述

一天，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

题目链接:HAUTOJ 1282

题意：求最大子段和的套路题，不过稍微变形了一点（变了一点点我就不会了  5555），就是构成了一个回环，需要加上首尾相连的情况，这时候我们可以用子段总和减去最小子段和，就是最大的子段和情况，题解思路是求相反子段和的最大子段和，最后用最大子段总和加上相反子段的最大子段和，其实和原来的那种思路一样，不过这种思路有局限性，就是只适合有正有负的情况，如果全部为正，则不能够满足条件

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define  N 55000
#define inf -99999999
int a[N],b[N];

long long Max(long long a,long long b)
{
	if(a>b)
		return a;
	return b;
}

int main()
{
	int i,n;
	long long sum,sum1,sum2,ans;
	while(scanf("%d",&n)!=EOF)
	{
		ans = inf;
		sum = 0;
		sum1 = sum2 = 0;
		for(i = 1; i <= n; i ++)
		{
			scanf("%d",&a[i]);
			b[i] = -a[i];
			sum += a[i];
		}
		for(i = 1; i <= n; i ++)
		{
			sum1 += a[i];
			sum2 += b[i];
			if(sum1 < 0)
				sum1 = 0;
			if(sum2 < 0)
				sum2 = 0;
			ans = Max(ans,sum1);
			ans = Max(ans,sum+sum2);
		}
		printf("%lld
",ans);
	}
	return 0;
}