# 11006: 【原1006】求和游戏

### 题目描述

author: 梁晨锦 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1006

## Input Format

$$-100 \leq a_i \leq 100$$

## Sample Input

5
3
-5
7
-2
8


## Sample Output

13


## Sample Input

3
-6
-9
-10


## Sample Output

Game Over


## Hints

• 感谢 曹宇 <caoyu601 at live.com>
• 感谢 Rozc <i at rozc.farm>

## CallMeInk's solution

# include<iostream>
using namespace std;

int main(){
int a[1000001];
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
int maxh=a[1];
int max=-1000;
for(int i=2;i<=n;i++){
if (maxh<0) {
if (maxh+a[i]>max) max=maxh+a[i];
maxh=a[i];}
else {
maxh += a[i];
if (maxh>max) max=maxh;
}
}
if (max>0) cout << max;
else cout << "Game Over" << endl;
return 0;
}


## FineArtz's solution

/* 求和游戏 */
#include <iostream>
using namespace std;

int main(){
int n, t;
cin >> n;
cin >> t;
int MinSum = t, CurSum = t, ans = t;
for (int i = 2; i <= n; ++i){
cin >> t;
CurSum += t;
ans = max(ans, CurSum - MinSum);
MinSum = min(MinSum, CurSum - t);
}
if (ans > 0) cout << ans << endl;
else cout << "Game Over" << endl;
//cout << ans << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"

using namespace std;

constexpr auto maxnum = 1000009;
constexpr int inf = 10000000;

//求解
template <class T>
T bilibili(T* input, int num) {
if (num == 1) return -inf;
else if (num == 2) return input[0] + input[1];
//分成两块
int center = num / 2;
T a = bilibili(input, num / 2), b = bilibili(input + num / 2, num - num / 2);
//寻找左右的最大值
T maxl = -inf, maxr = -inf, templ = 0, tempr = 0, count = 0;
for (int i = num / 2 - 1; i >= 0; i--) {
templ += input[i];
maxl = maxl < templ ? templ : maxl;
}
for (int i = num / 2; i < num; i++) {
tempr += input[i];
maxr = maxr < tempr ? tempr : maxr;
}
maxl += maxr;
T max = a > b ? a : b;
max = max > maxl ? max : maxl;
return max;
}
int input[maxnum];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

int n;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> input[i];
}
int ans = bilibili(input, n);
if (ans > 0) {
cout << ans << endl;
}
else {
cout << "Game Over" << endl;
}

return 0;
}


## WashSwang's solution

#include <cstdio>
#include <iostream>
using namespace std;
int last,cur,now=-500,maxn,n;
int main() {
scanf("%d%d",&n,&last);
for (int i=1;i<n;++i)
{
scanf("%d",&cur);
now=max(cur+now,cur+last);
last=cur;
if (now>maxn) maxn=now;
}
if (maxn) cout<<maxn<<endl;
else cout<<"Game Over"<<endl;
return 0;
}


## yyong119's solution

#include <iostream>
#include <cmath>
int num[1000001],pre[1000001];
int n,i,nmax,j,flag;
int main(){
using namespace std;
cin>>n;
if (n<=100){
for (i=1; i<=n; i++){
cin>>num[i];
num[i]+=num[i-1];
}
for (i=1; i<n; i++)
for (j=i+1; j<=n; j++) nmax=max(num[j]-num[i-1],nmax);
}else{
for (i=1; i<=n; i++) cin>>num[i];
for (i=1; i<=n; i++){
if (pre[i-1]+num[i]<0) flag=0;
else{
pre[i]=pre[i-1]+num[i];
flag++;
}
if ((pre[i]>nmax)&&(flag>=2)) nmax=pre[i];
}
}
if (nmax) cout<<nmax;else cout<<"Game Over";
return 0;
}