1006. 求和游戏
http://acm.sjtu.edu.cn/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
53-57-28
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
- #include <iostream>
- #include <string>
- using namespace std;
-
- int main()
- {
- int n; //数组长度
- cin>>n;
- int *p = new int[n]; //申请内存
- for(int i = 0; i < n ; i++) //输入数据
- {
- cin>>p[i];
- }
-
- //题目要求子数列长度最小为2
- int maxSum = 0, tempSum = 0,thisSum= 0;
- int down = 0; //thisSum<0 的子数列的下一个下标
- int maxRight = 0; //和大于0的最大子数列的右下标
- int maxLeft = 0; //和大于0的最大子数列的右下标
-
- for(int j = 0; j < n; j++)
- {
- thisSum +=p[j];
- if(thisSum > maxSum)
- {
- if(j == down)
- {
- //当序列中有出现一个正数左边是负数,且这个正数前面的thisSum<0
- //这时该子序列为 这个正数与左边数组成序列 或 这个正数与右边数组成序列
- //中序列和较大的那一个。
- if(down >0 && j < n-1)
- {
- //如果这个正数的位置不在开头和末尾
- if(thisSum + p[down -1] > thisSum + p[j+1])
- {
- tempSum = thisSum + p[down -1];
- if(tempSum > maxSum)
- {
- maxSum = tempSum;
- maxRight = j;
- maxLeft = down -1;
- }
- }
- else
- {
- tempSum = thisSum + p[j+1];
- {
- if(tempSum > maxSum)
- {
- maxSum = tempSum;
- maxRight = j+1;
- maxLeft = down;
- }
- }
- }
- }
- else if(down == 0 && j < n-1) //如果这正数出现在开头
- {
- tempSum = thisSum + p[j+1];
- if(tempSum > maxSum)
- {
- maxSum = tempSum;
- maxRight = j+1;
- maxLeft = down;
- }
- }
- else if(down> 0 && j == n-1) //如果这个正数出现在末尾
- {
- tempSum = thisSum + p[down -1];
- if(tempSum > maxSum)
- {
- maxSum = tempSum;
- maxRight = j;
- maxLeft = down-1;
- }
- }
-
- }
- else
- {
- maxSum = thisSum;
- maxRight = j;
- maxLeft = down;
- }
- }
- else if(thisSum < 0)
- {
- thisSum = 0;
- down = j+1;
- }
- }
-
- if(maxSum > 0 && maxRight - maxLeft>0) //依题目要求:子数列长度要大于1
- cout<<maxSum;
- else
- cout<<"Game Over";
-
- return 0;
- }
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。