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开始,因为可能是单独元素和最大

来源/分类