首页 > 代码库 > 最大子段和及其拓展
最大子段和及其拓展
1、最大子段和问题
问题定义:对于给定序列a1,a2,a3……an,寻找它的某个连续子段,使得其和最大(如果某子序列全是负数则定义该子段和为 0)。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。
·状态设计:
dp[i] (1 <= i <= N) 表示以 a[i] 结尾的最大连续子段和。
显然,dp[i] >= 0 (1 <= i <= N)
状态转移方程:dp[i] = max{dp[i-1] + a[i], 0} (2 <= i <= N)
(每个a[i]有两个决策:加入以a[i-1]为结尾的最大连续子段;重新开始一个子串)
下面是http://blog.csdn.net/niteip/article/details/7444973
的证明:
主要讨论这个问题的建模过程和子问题结构.时刻记住一个前提,这里是连续的区间
- 令b[j]表示以位置 j 为终点的所有子区间中和最大的一个
- 子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中
- 如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j],用之前最大的一个加上a[j]即可,因为a[j]必须包含
- 如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大,前面的负数必然不能使你更大
对于这种子问题结构和最优化问题的证明,可以参考算法导论上的“剪切法”,即如果不包括子问题的最优解,把你假设的解粘帖上去,会得出子问题的最优化矛盾.证明如下:
- 令a[x,y]表示a[x]+…+a[y] , y>=x
- 假设以j为终点的最大子区间 [s, j] 包含了j-1这个位置,以j-1为终点的最大子区间[ r, j-1]并不包含其中
- 即假设[r,j-1]不是[s,j]的子区间
- 存在s使得a[s, j-1]+a[j]为以j为终点的最大子段和,这里的 r != s
- 由于[r, j -1]是最优解, 所以a[s,j-1]<a[r, j-1],所以a[s,j-1]+a[j]<a[r, j-1]+a[j]
- 与[s,j]为最优解矛盾.
2.最大子矩阵
合并列上的数值,即可转化为一维的最大子段和问题
3.M子段和
未完待续
最大子段和及其拓展
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。