1006. 求和游戏

佚名 6年前 (2019-05-15) 随笔 346人围观抢沙发百度已收录

https://acm.sjtu.edu.cn/OnlineJudge/problem/1006

Description

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

Input Format

第1行：键的个数n。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

−100≤ai≤100−100≤ai≤100

对于70%的数据，2≤n≤1,0002≤n≤1,000

对于100%的数据，2≤n≤1,000,0002≤n≤1,000,000

Output Format

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

Sample Input

Sample Output

Sample Input

3
-6
-9
-10

Sample Output

Game Over

解

#include <iostream>
#include <stdio.h>
using namespace std;
int S[1000001] = {0};
 
int main(){
    //freopen("1.txt","r",stdin);
    int n;
    int num;
    cin >> n;
    cin >> S[0];
    for (int i = 1 ; i < n; i++){
        cin >> num;
        S[i] = S[i-1] + num;        
    }
    
    int min = S[0];
    int min_flag = 0; 
    int max = S[1];
    for (int i = 1; i < n; i++){
        if (min > S[i]){
            min = S[i];
            min_flag = i;
        }
        if (i - min_flag > 1 && S[i] - min > max)
            max = S[i]-min;
    }
    if(max <= 0)
        cout << "Game Over";
    else
        cout << max;
    return 0;
    
}