队列型DP【仅题目】

最大子序列和(maxsum)

问题描述

输入一个长度为n的整数序列(A1,A2,……,An),从中找出一段连续的长度不超过M的子序列,使得这个序列的和最大。

例如:

序列   1, -3, 5, 1, -2, 3

当M=2或3时,S=5+1=6;当M=4时,S=5+1+(-2)+3=7。

输入:

输入文件第一行一个整数n表示序列的长度,第二行n个整数,代表序列的元素。第三行一个整数表示M。

输出:

一个整数,即子序列的最大和。保证结果不超过longint范围。

输入样例:

6

1 -3 5 1 -2 3

3

输出样例:

6

数据范围:

50%的数据N,M<=1000

100%的数据N,M<=20000

 

 

 

 

页面: 1 2

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注