最大子矩陣和其實是最大子段和問題的二維推廣.即給定一個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 閱讀(3884)
評論(3) 編輯 收藏 引用 所屬分類:
算法設計