2008年11月24日 星期一

UVa 108 Maximum Sum

解題策略

這題AC的關鍵是時間,用暴力法O(n6) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n3) ,不過一般用O(n4) 就可以通過了。

我也是用 O(n4) 的解法,首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置,一旦給定了子矩陣後,就要 O(1) 時間得到子矩陣的和。

要達成這個目標可以透過 sum table 來達成,我說明一下我的方法, sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。


一旦建好 sum table,那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。

閒聊

最後執行時間0.052 過關....改天再將作法補完,我好睏....晚安。原本用暴力法去跑 100x100 的矩陣,竟然要253秒(大汗)。