題目：
描述
已知矩陣的大小定義為矩陣中所有元素的和滤馍。給定一個矩陣峰档，你的任務是找到最大的非空(大小至少是1 * 1)子矩陣继效。
比如黍判，如下4 * 4的矩陣
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩陣是
9 2
-4 1
-1 8
這個子矩陣的大小是15刺洒。
輸入
輸入是一個N * N的矩陣鳖宾。輸入的第一行給出N (0 < N <= 100)。再后面的若干行中逆航，依次（首先從左到右給出第一行的N個整數(shù)鼎文，再從左到右給出第二行的N個整數(shù)……）給出矩陣中的N2個整數(shù)，整數(shù)之間由空白字符分隔（空格或者空行）因俐。已知矩陣中整數(shù)的范圍都在[-127, 127]拇惋。
輸出
輸出最大子矩陣的大小。
樣例輸入
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
樣例輸出
15
這道題是求最大子序列（矩陣中的元素之和最大）女揭，相當于求最優(yōu)解蚤假，可以用動態(tài)規(guī)劃的思想（求最長子序列）。但矩陣是二維的吧兔，因此可以將矩陣的行壓縮通過求列上的最長子序列即可磷仰。
參考代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100+5;
int juzhen[N][N];
int dp[N];
int maxnumxulie(int n) {//求一維最長子序列之和;
int maxsum = dp[0];
int dp1[N];
dp1[0] = dp[0];
for (int i = 1;i < n;++i) {
dp1[i] = (dp1[i-1] + dp[i] > dp[i]) ? (dp1[i-1] + dp[i]) : dp[i];
if (dp1[i] > maxsum) maxsum = dp1[i];
}
//cout << maxsum << endl;
return maxsum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0;i < n;++i) {
for (int j = 0;j < n;++j) {
cin >> juzhen[i][j];
}
}
int maxsum = juzhen[0][0];//假定的最大值;
for (int i = 0;i < n;++i) {
memset(dp, 0, sizeof(dp));//從第i行開始計算;
for (int j = i;j < n;++j) {
for (int k = 0;k < n;++k) {
dp[k] += juzhen[j][k];//dp代表從第i行開始到第j行為止第k列上元素之和, 二維矩陣壓縮為一維數(shù)組;
}
//cout << dp[0] << endl;
int sum = maxnumxulie(n);//相當于將第i行到第j行范圍內每一列元素之和求出最長子序列之和;
if (maxsum < sum) {
maxsum = sum;
}
}
}
cout << maxsum << endl;
return 0;
}
