1006. 求和游戏

http://acm./OnlineJudge/problem/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

***********************************************************************************************************************************

Analyse

本文参考了 博客http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html

并根据本题目作出了改进（使其适用于子序列长度大于1的情况，且能求出子序列对应的下标）。

这题目是 求子序列和大于0的最子序列的问题，即一个数列中，找出其子数列的最大值。

Code

[cpp] view plaincopy

1. #include <iostream>  
2. #include <string>  
3. using namespace std;  
4.   
5. int main()  
6. {  
7.     int n;     //数组长度  
8.     cin>>n;  
9.     int *p = new int[n];    //申请内存  
10.     for(int i = 0; i < n ; i++)     //输入数据  
11.     {  
12.         cin>>p[i];  
13.     }  
14.   
15.     //题目要求子数列长度最小为2  
16.     int maxSum = 0, tempSum = 0,thisSum= 0;  
17.     int down = 0;   //thisSum<0 的子数列的下一个下标  
18.     int maxRight = 0;   //和大于0的最大子数列的右下标   
19.     int maxLeft = 0;    //和大于0的最大子数列的右下标   
20.   
21.     for(int j = 0; j < n; j++)  
22.     {  
23.         thisSum +=p[j];  
24.         if(thisSum > maxSum)  
25.         {  
26.             if(j == down)      
27.             {  
28.                 //当序列中有出现一个正数左边是负数，且这个正数前面的thisSum<0  
29.                 //这时该子序列为 这个正数与左边数组成序列 或 这个正数与右边数组成序列  
30.                 //中序列和较大的那一个。  
31.                 if(down >0 && j < n-1)  
32.                 {  
33.                     //如果这个正数的位置不在开头和末尾  
34.                     if(thisSum + p[down -1] > thisSum + p[j+1])      
35.                     {  
36.                         tempSum  = thisSum + p[down -1];  
37.                         if(tempSum > maxSum)  
38.                         {  
39.                             maxSum = tempSum;  
40.                             maxRight = j;  
41.                             maxLeft = down -1;  
42.                         }  
43.                     }  
44.                     else  
45.                     {  
46.                         tempSum = thisSum + p[j+1];  
47.                         {  
48.                             if(tempSum > maxSum)  
49.                             {  
50.                                 maxSum = tempSum;  
51.                                 maxRight = j+1;  
52.                                 maxLeft = down;  
53.                             }  
54.                         }  
55.                     }  
56.                 }  
57.                 else if(down == 0 && j < n-1)  //如果这正数出现在开头  
58.                 {  
59.                     tempSum = thisSum + p[j+1];  
60.                     if(tempSum > maxSum)  
61.                     {  
62.                         maxSum = tempSum;  
63.                         maxRight = j+1;  
64.                         maxLeft = down;  
65.                     }  
66.                 }  
67.                 else if(down> 0 && j == n-1) //如果这个正数出现在末尾  
68.                 {  
69.                     tempSum = thisSum + p[down -1];  
70.                     if(tempSum > maxSum)  
71.                     {  
72.                         maxSum = tempSum;  
73.                         maxRight = j;  
74.                         maxLeft = down-1;  
75.                     }  
76.                 }  
77.   
78.             }  
79.             else  
80.             {  
81.                 maxSum = thisSum;  
82.                 maxRight = j;  
83.                 maxLeft = down;  
84.             }  
85.         }  
86.         else if(thisSum < 0)  
87.         {  
88.             thisSum = 0;   
89.             down = j+1;  
90.         }  
91.     }  
92.   
93.     if(maxSum > 0 &&  maxRight - maxLeft>0) //依题目要求：子数列长度要大于1  
94.         cout<<maxSum;  
95.     else  
96.         cout<<"Game Over";  
97.   
98.     return 0;  
99. }