首页 > ACM题库 > 九度OJ > 九度-1077-最大序列和[解题代码]
2013
12-12

九度-1077-最大序列和[解题代码]

题目来源:2006年清华大学计算机研究生机试真题

题目描述:

给出一个整数序列S,其中有N个数,定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
对于S的所有非空连续子序列T,求最大的序列和。
变量条件:N为正整数,N≤1000000,结果序列和在范围(-2^63,2^63-1)以内。
 

输入:

第一行为一个正整数N,第二行为N个整数,表示序列中的数。

输出:

输入可能包括多组数据,对于每一组输入数据,
仅输出一个数,表示最大序列和。

样例输入:
5
1 5 -3 2 4

6
1 -2 3 4 -10 6

4
-3 -1 -2 -5
样例输出:
9
7
-1

cpp 代码如下:
#include <stdio.h>

long arr[1000001];
int main(){
	long N;
	while(scanf("%ld", &N) != EOF){
		for(long i=0; i<N; i++)
			scanf("%ld", &arr[i]);
//		__int64 start=0,end=0;
//		__int64 end2;
		long long tmpMax = 0;
		long long max = arr[0];
		for(long i=0; i<N; i++){
			tmpMax += arr[i];
			if(tmpMax > max)
				max = tmpMax;
//			if(tmpMax > 0 ){
//				end = i;
//
//			}else
				if(tmpMax < 0){
				tmpMax = 0;
			}


		}
		printf("%lld\n",max);
	}

	return 0;
}
/**************************************************************
	Problem: 1077
	User: coder
	Language: C++
	Result: Accepted
	Time:100 ms
	Memory:8832 kb
****************************************************************/

java 代码如下:

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n;
	static long[] arr;
	//static final long MAX = (long) (Math.pow(2, 63)-1);
	static final long MIN = -(long) (Math.pow(2, 63)-1);

	public static void main(String[] args) {
		//System.out.println(MAX+" "+MIN);
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			n = s.nextInt();
			arr = new long[n];
			int tag = 0;
			for(int i=0; i<n; i++){
				arr[i] = s.nextLong();
				if(arr[i] > 0)
					tag = 1;
			}
			long premax=0,max = MIN;
			if(tag == 1){
				for(int i=0; i<n; i++){
					premax += arr[i];
					if(premax < 0)
						premax = 0;
					if(max < premax)
						max = premax;
				}
				
			}else{
				Arrays.sort(arr);
				max = arr[n-1];
			}
				
			System.out.println(max);
		}
	}

}

/**************************************************************
	Problem: 1077
	User: coder
	Language: Java
	Result: Accepted
	Time:2120 ms
	Memory:100420 kb
****************************************************************/


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks