View Code of Problem 19

#include <iostream>
#include<stdio.h> 
#include<string.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {

	/*
	给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。
	输入有多组数据。每组数据第一行输入一个整数n(n<=10^6),第二行输入n个整数。n=0时程序结束。
	每组数据输出一个答案 
	-2 11 -4 13 -5 -2
	*/
	int n;
	while( scanf("%d" , &n) != EOF  ) {
		if( n <= 0 )
			break;
		int a[n];
		for(int i =0 ; i < n ; i++ )
			scanf("%d" , &a[i]);
		int max = a[0];
		for(int i = 0 ; i < n ; i++) {
			int sum = a[i];
			for(int j = i + 1 ; j < n ; j++) {
				sum += a[j];
				if(max < sum)
					max = sum;
			}
		}
		if(max < a[n - 1])
			max = a[n - 1];
		printf("%d\n" , max);
	}

	return 0;
}

Double click to view unformatted code.


Back to problem 19