上交OJ-1006. 求和游戏

1006. 求和游戏

---

Description

石柱上有一排石头键盘，每个键上有一个整数。请你在键盘上选择两个键，使这两个键及其之间的键上的数字和最大。如果这个最大的和不为正，则输出“Game Over"。

Input Format

第1行：键的个数n。

第2..n+1行：键上的数字整数 ai。

−100≤ai≤100
对于70%的数据，2≤n≤1,000
对于100%的数据，2≤n≤1,000,000

Output Format

一行，最大和或者”Game Over"。

Sample Input

5
3
-5
7
-2
8

Sample Output

13

Sample Input

3
-6
-9
-10

Sample Output

#### Game Over

分析

保存两个值：

• 任意连续数字最大值
• 从刚输入值和之前数字连续最大和，如果之前连续最大和小于0，则丢弃，将其设置为刚输入的值

#include <iostream>

using namespace std;

int main()
{
    int max, tmp_max;
    int p1=0,p2=0,p;
    int n;
    int i;
    cin>>n;
    cin>>p1>>p2;
    max=p1+p2;
    if(p2>max)
        tmp_max=p2;
    else
        tmp_max=max;
    for(i=2;i<n;i++) {
        cin>>p;
        if(tmp_max>0) {
            tmp_max=tmp_max+p;
            if(tmp_max>max)
                max=tmp_max;
        }
        else //如果从最后开始连续数字最大值小于0则丢弃
            tmp_max=p;
    }
    if(max>0)
        cout<<max;
    else
        cout<<"Game Over";
    return 0;
}