PKU 1050 To the Max

• 動的計画法
• 横方向でここからここまでの和というテーブルを作り、
• 縦方向でそれらを足し合わせる
• O(N^4)

int main() {
	int N;
	scanf("%d", &N);

	for (int row = 0; row < N; ++row) {
		for (int column = 0; column < N; ++column) {
			int value;
			scanf("%d", &value);
			matrix[row][column] = (char)value;
		}
	}

	for (int row = 0; row < N; ++row) {
		for (int left = 0; left < N; ++left) {
			int sum = 0;
			for (int right = left + 1; right <= N; ++right) {
				sum += matrix[row][right - 1];
				dp0[row][left][right] = (short) sum;
			}
		}
	}

	int bestSum = INT_MIN;
	for (int left = 0; left < N; ++left) {
		for (int right = left + 1; right <= N; ++right) {
			for (int top = 0; top < N; ++top) {
				int sum = 0;
				for (int bottom = top + 1; bottom <= N; ++bottom) {
					sum += dp0[bottom - 1][left][right];
					if (bestSum < sum) {
						bestSum = sum;
					}
				}
			}
		}
	}

	cout << bestSum << endl;
}