序列型DP【仅题目】

常见的动态规划模型——序列模型

 

一、最大连续子序列和

最大连续子序列(subsequence)

【问题描述】

给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。输出最大连续子序列的和。即求所有连续子序列中元素和最大的一个, 例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和为20。

 

【输入格式】

第1行给出正整数k( <= 1000 ),第2行给出k个整数,中间用空格分隔。

 

【输出格式】

一个整数,表示连续子序列的最大和。

 

【输入样例】

6

-2 11 -4 13 -5 -2

【输出样例】

20

 

【思考】

当正整数个数k变得很大(如k<=100000)时,程序该怎么编程?

设f[i]表示以ai为结束点的最大连续子序列和。

f[i]=max(f[i-1]+a[i], a[i]);

 

 

点赞

发表评论

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