随笔 - 85  文章 - 47  trackbacks - 0

常用链接

随笔分类

随笔档案

搜索

  •  

最新评论

最大子矩阵和其实是最大子段和问题的二维推广.即给定一个m行n列的矩阵,求其一个子矩阵,行数从r1~r2,列数从c1~c2,使之全部元素之和为最大.

我们可以将最大子段和的动态规划解法推广到上述二维情况.其基本思路为,若始行i1与末行i2已给定,则求以i1起始以i2结束的最大子矩阵之和,即等于一个一维的最大子段和问题,只不过这里的数组a中元素a[j]是第j列里从第i1行加到第i2行的所有元素之和. 令t[i1,i2]表示这个行从i1到i2的最大子矩阵和,则求全矩阵的最大子矩阵之和的问题就等于在1<=i1<=i2<=m的范围中使t[i1,i2]最大化.

显然上述算法的时间复杂度为O(m^2*n). 然而,容易看出,整个问题的解决本质上还是一个一维最大子段和的问题,而在另一个维度--行上面,则还是枚举所有的1<=i1<=i2<=m用打擂的方法比较出最大者.也就是说,此方法仍然只是在列这个维度上用到了动态规划.

有没有可能对两个维度进行联合的动态规划求解呢?

posted on 2007-03-23 15:18 w2001 阅读(3055) 评论(3)  编辑 收藏 引用 所属分类: 算法设计

FeedBack:
# re: 最大子矩阵和问题 2008-07-19 08:53 xianle
三四维可以此类推  回复  更多评论
  
# re: 最大子矩阵和问题 2009-04-03 11:15 伍学平
不错不错 一目了然!!!!!  回复  更多评论
  
# re: 最大子矩阵和问题[未登录] 2011-02-04 22:56 _飞寒
"有没有可能对两个维度进行联合的动态规划求解呢? "

我也想知道是否存在这样的方法  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理