1276: 求和游戏

Time Limit: 1 SecMemory Limit: 12 MB

Submit: 464Solved: 78

[Submit][Status][Web Board]

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;

}