dp最大子段和问题

发布于:2021-10-27 02:29:40

一、最大一段子段和问题
输入一列数字,输出这一列数字的最大子序列的和
首先问题分析
状态设计:
dp[i] (1 <= i <= N) 表示以 a[i] 结尾的最大连续子段和。
显然,dp[i] >= 0 (1 <= i <= N)
求解目标:
max{dp[i]} (1 <= i <= N)
状态转移方程:
dp[i] = max{a[i],0} (i = 1)
dp[i] = max{dp[i-1] + a[i], 0} (2 <= i <= N)
注意,当a[i]>dp[i-1]+a[i]时,则表明前面之和为负数,可以忽略,让之后的累加从当前a[i]开始进行累加。
二、最大二段子段和问题
考虑到最大二段子段和问题和一段子段和问题有些类似,则考虑能否用求最大一段子段和问题求该问题的解
状态设计:
dpL[i] 表示以 a[i] 结尾的最大连续子段和。
dpL[i] = max{∑a[x…i], 0},1 <= x <= i <= N
显然,dpL[i] >= 0 (1 <= i <= N)
dpR[i] 表示以 a[j] 开始的最大连续子段和。
dpR[j] = max{∑a[j…y], 0},1 <= j <= y <= N
显然,dpR[j] >= 0 (1 <= j <= N)
求解目标:
max{max{dpL[k]} + max{dpR[l]}} (1 <= k < l <= N)
状态转移方程:
dpL[i] = max{a[i],0} (i = 1)
dpL[i] = max{dpL[i ? 1] + a[i], 0} (2 <= i <= N)
dpR[j] = max{a[j],0} (j = N)
dpR[j] = max{dpR[j + 1] + a[j], 0}(1 <= j <= N-1)
三、最大M段子段问题
求给定一列数字最大M段子段和
状态设计:
dp[i][j]表示只由前 j 项组成的序列中以 a[j] 结尾的最大 i 子段和
求解目标:
dp[M][N]
状态转移方程:
d[i][j]表示前j项中i个字段和的最大值d[i][j]=max{d[i][j-1]+d[i-1]t}+num[j];

相关推荐

最新更新

猜你喜欢