先建立一個陣列 sumArr，使 sumArr[i][j + 1] = arr[i][0] + arr[i][1] + ... + arr[i][j]。換句話說，sumArr[i][j + 1] 是第 i 行 [0, j] 列的和，而 sumArr[k][j] - sumArr[k][i] 便是第 k 行 [i, j] 列的和。如此便能夠將問題轉化為求 i * j 個一維陣列的最大區段和，時間複雜度為 O(n^3)。
Let sumArr[i][j + 1] = arr[i][0] + arr[i][1] + ... + arr[i][j]. Thus, sumArr[i][j + 1] is the sum of rows [0, j] in column i, and sumArr[k][j] - sumArr[k][i] is the sum of rows [i, j] in column k. This way, the problem can be simplified to finding the maximum subsequence in i * j 1D-arrays, making the time complexity O(n^3).
UVa Link
#include <iostream>
int main() {
std::cin.tie(0);
std::ios_base::sync_with_stdio(0);
int n, arr[100][100], sumArr[100][101] = { 0 };
while (std::cin >> n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int in;
std::cin >> in;
arr[i][j] = in;
sumArr[i][j + 1] = sumArr[i][j] + in;
}
}
int max = -100000;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int sum = 0;
for (int k = 0; k < n; k++) {
sum += sumArr[k][j] - sumArr[k][i];
if (sum > max) max = sum;
if (sum < 0) sum = 0;
}
}
}
std::cout << max << '\n';
}
}