[UVA] 108 Maximum Sum

寫了一堆I/O題後，在108就卡住了。O(n^4)雖然可能會過，不過一看就知道不是正解。

一維的maximum subarray是有線性解的(Kadane)，但是我推不出二維的線性解。原本想法是用DP，讓ary[i][j] 記住從它開始往右往下 展開最大的矩形，然後想辦法湊出ary[i+1][j+1] = function(ary[i-1][j-1], ary[i-1][j], ary[i][j-1])的形式，結果發現似乎不可能有O(n^2)的解><

投降後上網查了一下，發現可以用暴力+Kadane做到O(n^3)解。簡單來說，就是想辦法把2D array compact成一維，然後再找一維的最大值。實作就是把所有的列組合 i ~ j, i < j 列舉，然後累加，例如 Rowi ~ Rowj的累加一維矩陣就是就是 compact[k] =  array[i][k] + array[i+1][k] + .. + array[j][k]。接著把compact丟近Kadane，求最大值，收工。

教訓就是當1D變成多維時，可以使用暴力列舉製作出所有1D的組合再套用1D的DP解。