問(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;
}
