Openjudge noi 1768 最大子矩阵

题目：

描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。
输出
输出最大子矩阵的大小。
样例输入
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
样例输出
15

这道题是求最大子序列（矩阵中的元素之和最大），相当于求最优解，可以用动态规划的思想（求最长子序列）。但矩阵是二维的，因此可以将矩阵的行压缩通过求列上的最长子序列即可。

参考代码：

#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列上元素之和, 二维矩阵压缩为一维数组;
            }
            //cout << dp[0] << endl;
            int sum = maxnumxulie(n);//相当于将第i行到第j行范围内每一列元素之和求出最长子序列之和;
            if (maxsum < sum) {
                maxsum = sum;
            }
        }
    }   
    cout << maxsum << endl;
    return 0;
}