火锅火锅和火锅（10分）
题目内容：
众所周知，沫沫以火锅为生。在E8的聚餐活动中，他经常卖萌卖无辜领着大家吃火锅。。
有一天，沫沫听说学校附近的哺呷哺呷在某现充的赞助下有一个优惠活动，只需30软妹币，对每个客人，它会上N道菜，但是客人只能挑选其中连续上的一些菜。
于是他非常兴奋的拉着灰灰和渣渣去吃火锅去啦。
沫沫是一个十分挑食的人，所以他对每一道菜都有一个愉快度（当然因为他的挑食，某些事物的愉快度会是负数）。
为了让沫沫能非常愉快的享受这次聚餐，善解人意的灰灰和渣渣决定帮他计算，他们应该怎么选择菜才能使沫沫最开心地吃完这次聚餐。
输入格式:
第一行是一个整数T，（T <= 10）表示测试案例的个数
对于每个测试案例，第一行是一个整数N，( 1<=N <= 10000)表示菜的个数
接下来的N个数字，第i个数字si表示沫沫对第i道菜的愉快度。（ -1000 <=si <= 1000）
PS:由于CF又被血虐掉rating，所以沫沫的起始愉快度是0
PPS:沫沫完全可能得到一个为负值的愉快值， poor 沫沫。。
输出格式：
对于每个样例，输出一个数字，表示沫沫吃完之后愉快度的最大值。
HINT ：
对于 5
6 -1 5 4 -7
我们选择6， -1， 5， 4这四道菜（注意必须是连续的，所以不能跳过-1）
做完后请思考,如果N的范围是1<=N<=100000呢？
输入样例：
2
5
6 -1 5 4 -7
7
0 6 -1 1 -6 7 -5
输出样例：
14
7时间限制：500ms内存限制：32000kb
首先，感谢丁zy助教的帮助！丁助教最帅了，魅力十足，yyds! 此外，放一个补充链接在结尾辅助理解。
想说的是，这道题的测试样例并不可靠！可能你写出了一段错误的代码，但是仍然通过了测试，如果只是想要代码，那么下面放出一段代码
错误的代码，不过可以通过测试
#include<stdio.h>
int main() {
int x,n,t,sum,len,max=-1001;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
sum=len=0;
while(n--) {
scanf("%d",&x);
if(max<x) max=x;
if(len+x>0) len=len+x;
else len=0;
if(sum<len) sum=len;
}
if(max<0) printf("%d\n",max);
else printf("%d\n",sum);
}
return 0;
}分析：
其实这道题的核心就是在于这个连续性问题的处理，那么，简单考虑（给的数据10000也有经过认真考虑，不是随意的），可以创立一个大小为10000的数组a[10000]。
假设愉悦度为joy = a[0], 那么来比较，joy 和 a[0] + a[1] 的大小，……到 a[0] + a[1] + …… + a[n-1]
然后从a[1]开始，比较joy 与 a[1], 一直到 ，a[1]+……+ a[n-1]
……
可以判断出joy的最大值
代码如下：
第一版
#include <stdio.h>
#include <string.h>
#define N 10000
int max(int a, int b);
int main()
{
int t = 0;
scanf("%d", &t);
while (t--) {
int a[N] = { 0 };
int n = 0;
scanf("%d", &n);
int i = 0;
while (n--)
scanf("%d", &a[i++]);
n = i;
int joy = a[0];
for (int i = 0; i < n; i++) {
int sum = a[i];
for (int j = i; j < n; j++) {
joy = max(joy, sum);
if(j != n-1) sum += a[j+1];
}
}
printf("%d\n", joy);
}
return 0;
}
int max(int a, int b)
{
return a > b ? a : b;
}再分析：可以看出，这个效率极低，所需要的时间长！
可以发现 a[0]+a[1]+ …… +a[i] = s[i]-s[0]+a[0]
根据一般归纳可得， a[m] + a[m+1] + …… + a[n] = s[n] - s[m] + a[m]， 连续的一段序列的和 等于 两个sum之差
依次从m=0 到 m = n, 来判断
可以写出类似的代码
观看其它同学的代码，发现新的思路，可以用 分治法
假设有n个数据，那么可以一分为2，n/2 与 n - n/2。那么 最大连续和就有三种情况：在左边，left；在右边,right; 横跨中间 ，cross
对于在左边、右边的，又可以继续采用分治法，也就是递归……
而如果在中间，那么就一定包含 n/2 和 n/2 + 1这些元素，然后一直向左，向右求最大值
根据这个思路，可以写出这样的代码：
第二版代码
#include <stdio.h>
#include <string.h>
#define N 10000
int max(int a, int b);
int maxsum(int a[], int x, int y);
int main(void)
{
int t = 0;
scanf("%d", &t);
while (t--) {
int a[N] = { 0 };
int n = 0;
scanf("%d", &n);
int i = 0;
while (n--)
scanf("%d", &a[i++]);
n = i;
int joy = a[0];
joy = maxsum(a, 0, n);
printf("%d\n", joy);
}
return 0;
}
int max(int a, int b)
{
return a > b ? a : b;
}
int maxsum(int a[], int x, int y) //a[x]<= <a[y]
{
if (y - x == 1) return a[x];
int m = x + (y - x) / 2;
int max_ans = max(maxsum(a, x, m), maxsum(a, m, y));
int left = a[m - 1], u = 0;
for (int i = m - 1; i >= x; i--) left = max(left, u += a[i]);
int right = a[m], v = 0;
for (int i = m; i < y; i++) right = max(right, v += a[i]);
return max(max_ans, left + right);
}
/*以{1，2，3，5，-4，-3，7}为例*/最后一版：好像已经很好了，但是我们又发现，由再分析中的代码可以收到启发。 如果要s[n] - s[m] + a[m]最大，相当于s[n] - s[m-1]，对于固定的n,只要s[m-1]最小即可！
也就是我们可以用一次循环找到s中最小的，这样可以再优化！当然，我发现这样的话占用内存太大了，不得不说，这是它的一个缺点！
第三版代码
#include <stdio.h>
#include <string.h>
#define N 10000
int max(int a, int b);
int main(void)
{
int t = 0;
scanf("%d", &t);
while (t--) {
int a[N] = { 0 };
int n = 0;
scanf("%d", &n);
int i = 0;
while (n--)
scanf("%d", &a[i++]);
n = i;
int joy = a[0];
//前n项和
int s[N] = { 0 };
s[0] = a[0];
for (int i = 1; i < N; i++) s[i] = s[i - 1] + a[i];
for (int i = 1; i < N; i++) {
int min = 0;
for (int j = 0; j < i; j++) {
min = (min < s[j]) ? min : s[j];
}
joy = joy<(s[i] - min) ? (s[i] - min) : joy;
}
printf("%d\n", joy);
}
return 0;
}
int max(int a, int b)
{
return a > b ? a : b;
}