poj: To the Max

To the Max.cpp

#include <cstdio>
#include <string>
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <cfloat>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

#define _MAX_ 100
int m_[_MAX_+1][_MAX_+1];

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int N, x;  int max_v = INT_MIN;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			scanf("%d", &x);
			m_[i][j] = x+m_[i-1][j];
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = i+1; j <= N; ++j) {
			int sum = 0;
			for (int k = 1; k <= N; ++k) {
				sum += m_[j][k] - m_[i][k];
				max_v = max(max_v, sum);
				if (sum < 0) sum = 0;
			}
		}
	}

	printf("%d", max_v);
	return 0;
}

思路

一维数组求子数组的最大和问题, 解法已知.
对于每一列的元素, 求出行i~j之间的元素之和, 即可把二维的子矩阵问题转化为一维的子数组问题. O(N^3)

Note

The numbers in the array will be in the range [-127,127]. 但是存放他们的一列和的矩阵不能是signed char