pku 1050 最大子矩阵和

题目大意：
给定一个N*N的矩阵，求其中一个子矩阵所有元素的和最大，输出最大值。

题解：
    这道题很早就见过了，一直不会做，学了最大连续和，但是没能成功迁移，看别人的解题报告也是很久才理解。
主要思想就是把二维的矩阵转化成一位的数字串，然后求最大子串和。转换的时候，为了保证最大子串构成的是完整的矩形，所以串里的每一个元素都得是一列的和。枚举子矩阵的起始行和高度，如从第i行开始，到第j行结束，每一对 i 和 j，对每一列(1~n)求和，然后求1~n串的最大子串和。
#include<stdio.h>
#include<string.h>
const int N = 110;
int g[N][N], f[N];
int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        memset(f, 0, sizeof(f));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d", &g[i][j]);
        int mx=-100000000;
        for(int i=1; i<=n; i++)
            for(int j=i ; j<=n; j++){
                memset(f, 0, sizeof(f));
                for(int s=1; s<=n; s++)
                    for(int k=i; k<=j; k++)
                        f[s]+=g[k][s];
                int tmp=0;
                for(int s=1; s<=n; s++){
                    if(tmp>0)
                        tmp+=f[s];
                    else
                        tmp=f[s];
                    mx=mx>tmp?mx:tmp;
                }
            }
        printf("%d\n",mx);

    }
    return 0;
}