描述
??
下雨了，下雨了，蚂蚁搬家了。
已知有n种食材需要搬走，这些食材从1到n依次排成了一个圈。小蚂蚁对每种食材都有一个喜爱程度值Vi，当然，如果Vi小于0的时候，表示蚂蚁讨厌这种食材。因为马上就要下雨了，所以蚂蚁只能搬一次，但是能够搬走连续一段的食材。时间紧急，你快帮帮小蚂蚁吧，让它搬走的食材喜爱值和最大。
-
输入
-
有多组测试数据（以EOF结尾）。
每组数据有两行，第一行有一个n，表示有n种食材排成了一个圈。（1 <= n<= 50000)
第二行分别有n个数，代表蚂蚁对第n种食材的喜爱值Vi。(-10^9 <= Vi <= 10^9) 输出
- 输出小蚂蚁能够搬走的食材的喜爱值总和的最大。 样例输入
-
3 3 -1 2 5 -8 5 -1 3 -9
样例输出
-
5 7
看完题目，很容易联想到最大子串和，只不是这个序列是环形的。现在给出n个数的序列，我们把第一个元素和最后一个元素定义为环相接的地方。
相接的地方的情况有四种情况
1.第一个元素是正数，最后一个元素是正数
2.第一个元素是正数，最后一个元素是负数
3.第一个元素是负数，最后一个元素是正数
4.第一个元素是负数，最后一个元素是负数
我们定义min_sum最小和的子串 max_sum是最大和的子串，sum是n和元素的和
那么，我们要求的ans =max(max_sum,sum-min_sum);
易知最大子序列和中是不包含最小子序列和的，所以，最大子序列和是不横跨连接处的最大和。那么总和sum-最小和min_sum就是横跨连接处的最大和。我们要求的最大和就是在这两个数中找到较大的那一个。
注意：数据范围。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50000+1
#define LL long long
using namespace std;
LL v[N],dp1[N],dp2[N];
LL n,max_sum,min_sum,sum;
int main(){while(scanf("%lld",&n)!=EOF){//初始化数组 memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2));sum=0;for(int i=1 ;i<=n ;i++){scanf("%lld",&v[i]);sum+=v[i];//元素总和 dp1[i] = max(dp1[i-1]+v[i],v[i]);dp2[i] = min(dp2[i-1]+v[i],v[i]);}max_sum=-9999999;min_sum=9999999;//求最大和与最小和 for(int i=1 ;i<=n ;i++){max_sum = max(max_sum,dp1[i]);min_sum = min(min_sum,dp2[i]);}LL ans = max(max_sum,sum-min_sum);printf("%lld\n",ans);}return 0;
}??