最大子矩阵和其实是最大子段和问题的二维推广.即给定一个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 阅读(3739)
评论(3) 编辑 收藏 引用 所属分类:
算法设计