Created
October 31, 2013 16:36
-
-
Save zsh-89/7252824 to your computer and use it in GitHub Desktop.
poj: To the Max
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
思路
一维数组求子数组的最大和问题, 解法已知.
对于每一列的元素, 求出行i~j之间的元素之和, 即可把二维的子矩阵问题转化为一维的子数组问题. O(N^3)
Note
The numbers in the array will be in the range [-127,127]. 但是存放他们的一列和的矩阵不能是signed char