pku 1050 最大子矩陣和

題目大意：
給定一個(gè)N*N的矩陣，求其中一個(gè)子矩陣所有元素的和最大，輸出最大值。

題解：
    這道題很早就見(jiàn)過(guò)了，一直不會(huì)做，學(xué)了最大連續(xù)和，但是沒(méi)能成功遷移，看別人的解題報(bào)告也是很久才理解。
主要思想就是把二維的矩陣轉(zhuǎn)化成一位的數(shù)字串，然后求最大子串和。轉(zhuǎn)換的時(shí)候，為了保證最大子串構(gòu)成的是完整的矩形，所以串里的每一個(gè)元素都得是一列的和。枚舉子矩陣的起始行和高度，如從第i行開(kāi)始，到第j行結(jié)束，每一對(duì) i 和 j，對(duì)每一列(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;
}