http://acm./OnlineJudge/problem/1006

Description

石柱上有一排石頭鍵盤(pán)，每個(gè)鍵上有一個(gè)整數(shù)。請(qǐng)你在鍵盤(pán)上選擇兩個(gè)鍵，使這兩個(gè)鍵及其之間的鍵上的數(shù)字和最大。如果這個(gè)最大的和不為正，則輸出“Game Over"。

Input Format

第1行：鍵的個(gè)數(shù)n。

第2..n+1行：鍵上的數(shù)字整數(shù) ai。

100≤ai≤100

對(duì)于70%的數(shù)據(jù)，2≤n≤1,000

對(duì)于100%的數(shù)據(jù)，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

并根據(jù)本題目作出了改進(jìn)（使其適用于子序列長(zhǎng)度大于1的情況，且能求出子序列對(duì)應(yīng)的下標(biāo)）。

這題目是 求子序列和大于0的最子序列的問(wèn)題，即一個(gè)數(shù)列中，找出其子數(shù)列的最大值。

Code

[cpp] view plaincopy

1. #include <iostream>  
2. #include <string>  
3. using namespace std;  
4.   
5. int main()  
6. {  
7.     int n;     //數(shù)組長(zhǎng)度  
8.     cin>>n;  
9.     int *p = new int[n];    //申請(qǐng)內(nèi)存  
10.     for(int i = 0; i < n ; i++)     //輸入數(shù)據(jù)  
11.     {  
12.         cin>>p[i];  
13.     }  
14.   
15.     //題目要求子數(shù)列長(zhǎng)度最小為2  
16.     int maxSum = 0, tempSum = 0,thisSum= 0;  
17.     int down = 0;   //thisSum<0 的子數(shù)列的下一個(gè)下標(biāo)  
18.     int maxRight = 0;   //和大于0的最大子數(shù)列的右下標(biāo)   
19.     int maxLeft = 0;    //和大于0的最大子數(shù)列的右下標(biāo)   
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.                 //當(dāng)序列中有出現(xiàn)一個(gè)正數(shù)左邊是負(fù)數(shù)，且這個(gè)正數(shù)前面的thisSum<0  
29.                 //這時(shí)該子序列為 這個(gè)正數(shù)與左邊數(shù)組成序列 或 這個(gè)正數(shù)與右邊數(shù)組成序列  
30.                 //中序列和較大的那一個(gè)。  
31.                 if(down >0 && j < n-1)  
32.                 {  
33.                     //如果這個(gè)正數(shù)的位置不在開(kāi)頭和末尾  
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)  //如果這正數(shù)出現(xiàn)在開(kāi)頭  
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) //如果這個(gè)正數(shù)出現(xiàn)在末尾  
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) //依題目要求：子數(shù)列長(zhǎng)度要大于1  
94.         cout<<maxSum;  
95.     else  
96.         cout<<"Game Over";  
97.   
98.     return 0;  
99. }