問(wèn)題描述
　　給定一個(gè)n*m的矩陣A，求A中的一個(gè)非空子矩陣，使這個(gè)子矩陣中的元素和最大。

　　其中，A的子矩陣指在A中行和列均連續(xù)的一塊。
輸入格式
　　輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示矩陣A的行數(shù)和列數(shù)。
　　接下來(lái)n行，每行m個(gè)整數(shù)，表示矩陣A。
輸出格式
　　輸出一行，包含一個(gè)整數(shù)，表示A中最大的子矩陣中的元素和。
樣例輸入
3 3
-1 -4 3
3 4 -1
-5 -2 8
樣例輸出
10
樣例說(shuō)明
　　取最后一列，和為10。
數(shù)據(jù)規(guī)模和約定
　　對(duì)于50%的數(shù)據(jù)，1<=n, m<=50；
　　對(duì)于100%的數(shù)據(jù)，1<=n, m<=500，A中每個(gè)元素的絕對(duì)值不超過(guò)5000。

之前學(xué)過(guò)最大子序列的求法：
要求一個(gè)序列中和最大的連續(xù)的子序列，那么需要滿足一下幾步：
1，子序列的第一個(gè)數(shù)大于1。
2，從第一個(gè)大于0的數(shù)開(kāi)始累加，不斷記錄最大的和。
3，如果出現(xiàn)和小于0，那么說(shuō)明負(fù)數(shù)值已經(jīng)足夠多，該記錄不再繼續(xù)，重新開(kāi)始累加。
總結(jié)成代碼函數(shù)實(shí)現(xiàn)：

int sub_sum(int *b)
{
    int s,max;
    s = max = b[1];
    int i;
    for(i=2;i<=n;i++)
    {
        s += b[i];
        if(s > max)
            max = s;
        if(s < 0)
            s = 0;
    }
    return max;
}

而當(dāng)最大子序列擴(kuò)展為最大矩陣時(shí)，暴力破解必定是超時(shí)的，這時(shí)需要用到該知識(shí)點(diǎn)進(jìn)行擴(kuò)展從而求解。
思路如下：
1，所求的子矩陣必須是每一行數(shù)字個(gè)數(shù)都相等，每一列的數(shù)字個(gè)數(shù)也相等。
2，假設(shè)都是固定的列數(shù)，可以將每一列都加和存入數(shù)組，那么得到的就是一個(gè)一維的數(shù)組，把這個(gè)數(shù)組求最大子序列即可。
3，既然是在一個(gè)矩陣中求解的，所以子矩陣的列數(shù)范圍在原矩陣的列數(shù)范圍之內(nèi)，用列舉方法即可。
具體圖解如下：

表示，從第一行，第一，二行，到從第一行到最后一行，每次都取各列的和存入數(shù)組，求解最大子序列。
從第二行，第二，三行，到從第二行到最后一行，每次都取各列和存入數(shù)組，求最大子序列。
一直到最后一行，求最大子序列。
最大子序列中求解最大值，即是所求的解。

整理成代碼求解：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 501
int a[N][N];
int n,m;
int sub_sum(int *b)//求最大子序列
{
    int s,max;
    s = max = b[1];
    int i;
    for(i=2;i<=n;i++)
    {
        s += b[i];
        if(s > max)
            max = s;
        if(s < 0)
            s = 0;
    }
    return max;
}
int main()
{
    int i,j,t,maxsum,s;
    int *b;
    scanf("%d%d",&n,&m);
    b = (int *)malloc(sizeof(int)*(n+1));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    maxsum = a[1][1];
    for(i=1;i<=m;i++)
    {
        memset(b,0,(n+1)*sizeof(int));
        for(j=i;j<=m;j++)
        {
            //固定i,j列
            for(t=1;t<=n;t++)
                b[t] += a[t][j];//自底向上(固定列m,m,n(固定行n,n,m))
            s = sub_sum(b);
            if(s > maxsum)
                maxsum = s;
        }
    }
    printf("%d\n",maxsum);
    return 0;
}