題目：http://poj.org/problem?id=1050
輸入一個n*n的整數方陣(n到100)，求最大子矩陣和
程式碼：http://codepad.org/gTlEgrmT
經典DP，O(n^3)解
先來考慮一種非常特別的矩陣：當它退化成數列的時候
[ 10 -5 7 -99 20 ]
這樣的最大子矩陣和，顯然就是最大連續元素和(像上面這個例子答案是20)
現在怎麼樣把連續元素和推廣到二維的情形呢？
我們考慮把數列元素「壓扁」變成一列、進行最大連續元素和
好比說範例測資
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
例如把第二列和第三列壓扁，得到[5 3 -10 3]，答案是8
這時候會有很多種不一樣的壓扁方法
那就...枚舉全部的壓扁方法從第i列壓到第j列
然後各自作連續元素和，取出最大的一個當作答案
最後需要特別注意這裡空矩陣不算是一種子矩陣(在怎麼爛都要取至少一個元素)
沒有留言:
張貼留言