1276: 求和游戏
Time Limit: 1 SecMemory Limit: 12 MB
Submit: 464Solved: 78
Description
小明有n个球排成一行，每个球上有个数字。现在小明选择两个球，使这两个球及其这两个球之间的数字和最大。如果这个最大的和不为正，则输出“Game Over”。
Input
第一行输入T，有T组数据。
每组数据：输入n（1<n<1000000 ），再输入n个整数，表示第1个球到第n个球上的数字，每个球上的数字大于-100，小于100。
Output
对于每组数据，输出最大和或者”Game Over“，占一行。
Sample Input
6
5
3 -5 7 -2 8
3
-1 2 3
4
-1 1 -111 1111
3
-1 -2 -3
3
1 -1 0
6
100 -1 -1 -1 -1 -1 -1
Sample Output
13
5
1001
Game Over
Game Over
99
1276: 求和游戏 - tb_youth的博客 - CSDN博客
动态规划
先把这个问题分解为3个数的子问题，
假设这上三个数：a1 a2 a3
要 求解这组数据中 区间的最大和
这组数据有这三种情况：
a1 a2
a2 a3
a1 a2 a3
仔细想想，如何模拟这三种情况：
先设定
sum = a1 + a2；
maxs = sum；
那就成了加上a3之前要不要舍弃a1这问题了，
那什么时候应该舍弃a1？
如果a1是个负值，那肯定要舍弃掉它，如何判断呢?如果sum > a2 ，a1肯定是个正数，==的话a1=0，舍不舍弃都没关系，<的话肯定是个负数，所以如果
sum < a2,就sum = sum - a1 + a3（第一个个区间和用maxs存好了），否则sum = sum + a3；
因为后两种情况只会取其一（而且是更大的那个，取决于a1是否>0）
那么：
ans = max（maxs,sum）
子问题解决了，类推就行
作者：tb_youth
原文：https://blog.csdn.net/tb_youth/article/details/86651119
#include <stdio.h>
int a[1000005];
int main()
{
int n,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
double sum = a[0] + a[1],maxsum = sum;
for(int i = 2; i < n; i++)
{
sum > a[i-1] ? sum += a[i] : sum = a[i-1] + a[i];
sum > maxsum ? maxsum = sum : maxsum = maxsum;
}
if(maxsum > 0)
printf("%.0lf\n",maxsum);
else
printf("Game Over\n");
}
return 0;
}
