範例程式碼 uva108

//uva108
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int max_sum = INT_MIN;
    int N = 0, sum = 0;
    vector<vector<int> > matrix, col_dp(matrix);
    while (cin >> N && N) {
        max_sum = INT_MIN;
        matrix.assign(N + 1, vector<int>(N, 0));
        col_dp.assign(matrix.begin(), matrix.end());

        // Input
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> matrix[i][j];
            }
        }

        // Create column dp table
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < N; j++) {
                col_dp[i][j] = col_dp[i - 1][j] + matrix[i][j];
            }
        }

        // List all possible situations
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                sum = 0;
                for (int k = 0; k < N; k++) {
                    sum += col_dp[j][k] - col_dp[i - 1][k];
                    if (sum > max_sum) {
                        max_sum = sum;
                    }
                    if (sum < 0) {
                        sum = 0;
                    }
                }
            }
        }
        cout << max_sum << endl;
    }
    return 0;
}