首页 > 代码库 > 最大子段和及其拓展

最大子段和及其拓展

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子段和

未完待续

最大子段和及其拓展