2734: 最大连续子段和以及个数
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:30
解决:9
题目描述
(最大连续子段和) 给出一个数列(元素个数不多于 100),数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多,并输出这个最大和以及该连续子数列中元素的个数。例如数列为4,-5,3,2,4 时,输出 9 和 3;数列为 1,2,3,-5,0,7,8时,输出 16 和 7。
输入
数字个数n,以及n个数值
输出
最大和以及该连续子数列中元素的个数
样例输入 复制
5
4 -5 3 2 4
样例输出 复制
9 3
提示
此题多种解法: 尺取法、DP、前缀
前缀和:在数据量不大的情况下,前缀和用双重循环枚举是可以的,注意j从i开始,因为可能是单独元素和最大
前缀和:在数据量不大的情况下,前缀和用双重循环枚举是可以的,注意j从i开始,因为可能是单独元素和最大