题库 信息学奥赛题库 题目列表 (最大连续子段和)给出一个数列(元素个数不多于 100...
组合题

(最大连续子段和)给出一个数列(元素个数不多于 100),数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列,

使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多,

并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4,−5,3,2,4 时,输出 9 和 3;数列为 1,2,3,−5,0,7,8 时,输出 16 和 7。

#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg,end;
int main() {
	cin >> n;
	for (i=1; i<=n; i++)
		cin >> a[i];
	tmp=0;
	ans=0;
	len=0;
	beg=     ①     ;
	for (i=1; i<=n; i++) {
		if (tmp+a[i]>ans) {
			ans=tmp+a[i];
			len=i-beg;
		} else if (        ②         &&i-beg>len)
			len=i-beg;
		if (tmp+a[i]    ③     ) {
			beg=     ④     ;
			tmp=0;
		} else
			⑤        ;
	}
	cout << ans << " " << len << endl;
	return 0;
}
第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
阅读程序 2009年 初赛
-
正确率
0
评论
19
点击
QQ
微信