首页 > 代码库 > 求和游戏——java

求和游戏——java

2024-07-08 15:19:09   225人阅读

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


这道题说实话，我感到很难，当时想着是，如果自己去遍历所有情况然后去求和求最大值，这肯定不行，有太多的重复求和了，如果去把算过的存起来又是那么的不靠谱，百度了一下，真心觉得大神就是大神，竟然有人那么牛逼的实现。
这道题我们先来看看怎样实现最大子列，这个的复杂度是线性的，只需要n
代码如下：
                int curSum=0;		int res=0;		int minSum=0;		for(int i=0;i<n;i++){			int temp =in.nextInt();			curSum+=temp;			res = res>(curSum-minSum)?res:(curSum-minSum);			minSum = minSum<curSum?minSum:curSum;		}

　但是这道题是求至少包含两个数的最大子列所以做很简单的改动

　

minSum = minSum<(curSum-temp)?minSum:(curSum-temp);

　　完整代码如下：

import java.util.Scanner;public class Main {		private static Scanner in;	public static void main(String[] args) {		in = new Scanner(System.in);		int n=in.nextInt();		int curSum=0;		int res=0;		int minSum=0;		for(int i=0;i<n;i++){			int temp =in.nextInt();			curSum+=temp;			res = res>(curSum-minSum)?res:(curSum-minSum);			minSum = minSum<(curSum-temp)?minSum:(curSum-temp);		}		if(res>0){			System.out.println(res);		}else{			System.out.println("Game Over");		}	}}

　　


联系
我们