Maximum Sum

大意：给你一个n*n的矩阵，求最大的子矩阵的和是多少。

思路：最開始我想的是预处理矩阵，遍历子矩阵的端点，发现复杂度是O(n^4)。就不知道该怎么办了。问了一下，是压缩矩阵，转换成最大字段和的问题。

压缩行或者列都是能够的。

int n, m, x, y, T, t;

int Map[1010][1010];

int main()

{

    while(~scanf("%d", &n))

    {

        memset(Map, 0, sizeof(Map));

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

        {

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

            {

                scanf("%d", &t);

                Map[i][j] = Map[i-1][j]+t;

            }

        }

        int Max = -INF;

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

        {

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

            {

                int sum = 0;

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

                {

                    sum = sum<0?

0:sum;

                    sum += Map[j][k]-Map[i-1][k];

                    Max = max(sum, Max);

                }

            }

        }

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

    }

    return 0;

}