题意：一个N * N的矩阵，求子矩阵的最大和(N <= 100, -127 <= 矩阵元素 <= 127)。

题目链接：http://poj.org/problem?id=1050

——>>将二维压缩为一维。对一维进行dp求解。

将二维压缩成一维：

1、第1行

2、第2行加第1行

3、第3行加第2行加第1行

……

N、第N行加第N-1行加……加第1行

1、第2行

2、第3行加第2行

……

1、第N行

对于一维情况。设dp[i]表示以第i个元素结尾的最大连续和，则状态转移方程为：

dp[i] = max(nBuf[i], dp[i - 1] + nBuf[i]);

加上滚动数组思想优化空间。。

总时间复杂度：O(N ^ 3)

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::max;

const int MAXN = 100 + 1;

const int INF = 0x3f3f3f3f;

int N;

int nMatrix[MAXN][MAXN];

void Read()

{

    for (int i = 1; i <= N; ++i)

    {

        for (int j = 1; j <= N; ++j)

        {

            scanf("%d", &nMatrix[i][j]);

        }

    }

}

void Dp()

{

    int nRet = -INF;

    int nBuf[MAXN];

    for (int i = 1; i <= N; ++i)

    {

        memset(nBuf, 0, sizeof(nBuf));

        for (int j = i; j <= N; ++j)

        {

            for (int k = 1; k <= N; ++k)

            {

                nBuf[k] += nMatrix[j][k];

            }

            int dp = 0;

            for (int k = 1; k <= N; ++k)

            {

                dp = max(nBuf[k], dp + nBuf[k]);

                nRet = max(nRet, dp);

            }

        }

    }

    printf("%d\n", nRet);

}

int main()

{

    while (scanf("%d", &N) == 1)

    {

        Read();

        Dp();

    }

    return 0;

}