POJ 1050 To the Max

借助前缀和，将二维的最大子矩阵转化为一维的最大子段和问题。

需要枚举最大子矩阵的首行和末行，内层循环每次都要求一遍最大子段和，时间复杂度为：(O(n^3))

const int N = 110;
int a[N][N];
int f[N][N];
int n;

int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                cin >> a[i][j];
                a[i][j] += a[i-1][j];
            }

        int ans = -INF;
        for(int i = 1; i <= n; i++)  // 枚举最大子矩阵所在的第一行
            for(int j = i; j <= n; j++)  // 枚举最大子矩阵所在的最后一个行
            {
                int sum = 0, res = -INF;
                for(int k = 1; k <= n; k++)
                {
                    int x = a[j][k] - a[i-1][k];
                    sum = max(sum + x, x);
                    res = max(res, sum);
                }

                ans = max(ans, res);
            }

        cout << ans << endl;
    }
    //system("pause");
    return 0;
}