最大上升子序列(最大递增子段和)

452

没有找到相似的叫法,网上能搜到的有:
  • 最大递增子段和
  • 最大上升子段和

不过我更倾向于最大递增子段和

因为其算法与**>动态规划版的最大上升子序列<**如出一辙

根据名字可以看出,最大上升子序列的意义为:
找出一个数列的递增子列中,和最大的那个子列


采用动态规划的解法:
a[i] 来存储数列的第 i 个数
dp[i] 来记录到数列的第 i 个数(选取它的情况下)

对于数列中的第 i 个数,显然有 i 种可能:


1. 子序列上一个是 1

2. 子序列上一个是 2

3. 子序列上一个是 3

4. 子序列上一个是 4

……

i. 从 i 开始



而显然,由于子序列要上升,因此如果 a[j] <= a[i] 这种情况可以直接跳过的

也即 dp[i] = max{ dp[j]+a[i] } (j<i && a[j]<a[i])

由于最后可以从任意地方结束,因此答案不是 dp[n] 而是 dp[] 中最大的值
可以维护一个 Max 变量

数据为 1~n
a[0] 表示起点,初始化为 0

int Max = 0;
a[0] = 0;
for(int i = 0;i <= n;i++) {
dp[i] = 0;
for(int j = 0;j < i;j++)
if(a[i] > a[j])
dp[i] = max(dp[i],dp[j] + a[i]);
Max = max(Max,dp[i]);
}
发布评论
  • 点击查看/关闭被识别为广告的评论