主題
題目連結：
題目大意：
給定一正整數 N （N ≦ 100），代表接下來有 N ^ 2 個整數。代表著一個 N × N 的二維陣列之內容。
請找出此陣列的子區域中總和最大的那塊之和為多少？
（注：這題在 UVa 原始題目敘述中有提及至少要選出大小 1 × 1 的子區域，因此不可以什麼都不選）
例如：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
中和最大的子區域為
9 2
-4 1
-1 8
其總和為 15 。
範例輸入：
4
0 -2 -7 0 9 2
-6 2 -4
1 -4 1 -1 8 0
-2 10 9 116 24 -121 30 14 2 119 122 28 -53 125 -71 87 -57 42 -111 125
-33 91 -121 30 -28 1 -16 97 -11 68 -24 103 -126 98 -61 33 48 109
-88 67 -72 77 -107 95 -78 23 -86 45 -4 28 -121 73 -57 20 -122 9
68 -97 79 -68 122 -42 88 -22 0 -116 55 -44 68 -109 43 -32 103 -54
122 -41 62 -114 113 -32 29 -22 99 -11 38 -60 88 -83 28 -83 122 -56
100 -86 63 -49 111 -77 91 -88 69 -110
範例輸出：
15
963
解題思維：
這題實際上就是二維版本的最大連續子序列和。
例如：陣列
0 -2 -7
9 2 -6
-4 1 -4
將其拆成
0
9
-4
0 -2
9 2
-4 1
0 -2 -7
9 2 -6
-4 1 -4
-2
2
1
-2 -7
2 -6
1 -4
-7
-6
-4
這六種子陣列。並將每列各自加總變成：
0 、 9 、 -4 ；
-2 、 11 、 -3 ；
-9 、 5 、 -7 ；
-2 、 2 、 1 ；
-9 、 -4 、 -3 ；
-7 、 -6 、 -4
以上這六個一維的序列。因此，就可以套上最大連續子序列的作法，例如這題的前半部分。
之後，看哪個子陣列得出的結果值最大，即是所求。
而為了快速得到每列的第 i 、 j 個元素和，可以使用前綴和（Prefix Sums）的概念去求。例如像是這題。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
