C - 娜娜梦游仙境系列——吃不完的糖果
Problem Description
娜娜好不容易才在你的帮助下"跳"过了这个湖，果然车到山前必有路，大战之后必有回复，大难不死，必有后福！现在在娜娜面前的就是好多好多的糖果还有一些黑不溜秋的东西！不过娜娜眼中只有吃不完的糖果！娜娜高兴地快要蹦起来了！
这时有一位挥着翅膀的女孩（天使？鸟人？）飞过来，跟娜娜说，这些糖果是给你的~（娜娜已经两眼放光）~你可以带走~（娜娜已经流下了口水）~但是~（神马？还有但是？）~这位神仙姐姐挥一挥翅膀~飘过了一片云彩，糖果和那些黑不溜秋的东西顿时飞了起来，落到地上成了摆成一个奇怪的图形。
神仙姐姐很满意，转过来对娜娜说：“这些糖果和黑洞（神马？黑洞？）分成n堆，每堆要么都是糖果，要么是黑洞，围成一个圈（即第1堆的旁边是第n堆和第2堆），你可以选择连续若干堆，然后带走，不过这些黑洞嘛，会馋嘴的小孩吸进去，你必须拿糖果去中和掉。”
娜娜喜欢糖果，但不喜欢动脑子~于是就把这个问题交给你，怎样才能让娜娜带走最多的糖果呢？
Input
多组数据，首先是一个正整数t（t<=20）表示数据组数
对于每组数据，包括两行，第一行是一个正整数n（3<=n<=100000）表示堆数
第二行是n个整数x[i](1<=|x[i]|<=1000)，如果是个正整数，则说明这是一堆数量为x[i]的糖果，如果是个负整数，则说明这是一个需要用abs(x[i])颗糖果去中和的黑洞。
Output
Sample Input
3
5
1 2 3 4 5
5
1 -2 3 -4 5
5
-1 -2 -3 -4 -5
Sample Output
15
7
0
Hint
对于样例1，娜娜可以把所有的糖果都拿走，所以输出15(=1+2+3+4+5)
对于样例2，娜娜可以拿走第1,2,3,5堆的糖果，别忘了这是摆成一个圈，所以输出7(=1+(-2)+3+5)
对于样例3，等待娜娜的是5个黑洞，可怜的娜娜，一个糖果都拿不掉，所以输出0
由于输入数据较多，请谨慎使用cin/cout
题目在于找最大环串和的，在于用DP[i]求最大子串和的方法的扩展。要找到最大环和的子串，要么存在于0~N的最大连续子串中，要是么超过边界N~0，则可以知道，在0~N之间存在一段最小子串和，去除这一段的最小子串和，便是最大子串和。这一题在于找出最大子串和和最小子串和，最大子串和的求法在于 ,DP[i]记录以i为结尾的子串的最大和, DP[i]=MAX(DP[i-1]+Num[i],Num[i]),，要求最小子串和的话，我们只需要对原本数据取相反数，在求一次最大子串和，便可以知道其1~N之间的最小子串和为多少，然后去掉这一段只需要（将原来的数据的总和+这一段最小子串和）既可。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
using namespace std;
int N;
int DP[];
int Num1[];
int Num2[];
int Search_DP(int Num[])
{
int Max=;
int DP[]; /*DP[i]记录以i为结尾的子串的最大和*/
DP[]=Num[];
for(int i=;i<N;i++)
{
DP[i]=MAX(DP[i-]+Num[i],Num[i]);/*DP[i]等于（DP[i-1]+Num[i]或者是Num[i]）*/
Max=MAX(DP[i],Max); /*DP[i]等于（DP[i-1]+Num[i]或者是Num[i]）*/
}
return Max;
}
int main()
{
int T,Max;
int Max1;
int Max2,sum;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
sum=;
for(int i=;i<N;i++)
{
scanf("%d",&Num1[i]);
sum+=Num1[i];
Num2[i]=-Num1[i]; /*Num2[i]存Num1[i]原本数据的相反数*/ }
Max1=Search_DP(Num1); /*用动态规划DP求最大子串和的*/
Max2=Search_DP(Num2)+sum; /*求Num1的最小子串和《=》对其相反数求最大子串和*/
Max=MAX(Max1,Max2);
printf("%d\n",Max); }
}