求最大连续子矩阵和问题

可以转化为求最大连续子序列问题

map[i][j]=map[0][j]+map[1][j]+...+map[i][j]

即将第 j 列前 i 行的值压缩到map[i][j]

求第 x 行到第 y 行之间最大连续矩阵和，就将 x~y 行同列元素当成一个元素处理

这样就将 x~y 行压缩成了一行。再求最大连续子序列

若有4行

分别将第 1,  1和2,  1和2和3,  1和2和3和4,  2和3,  2和3和4,  3和4,  4 行压缩为一行 

代码如下：

#include
      
       int map[105][105];int main(){    int n,i,j,k;    while(scanf("%d",&n)!=EOF)    {        int t;        for(i=1; i<=n; i++)            for(j=1; j<=n; j++)  //读数据时就压缩            {                scanf("%d",&t);                map[i][j]=map[i-1][j]+t;            }        int max=0;        for(i=1; i<=n; i++)    //三个循环求所有压缩情况中的最大值        {            for(j=i; j<=n; j++)            {                int s=0;                for(k=1; k<=n; k++)    //k 控制列                {                    s+=map[j][k]-map[i-1][k];  // i~j 行压缩为一行，求最大连续子序列                    if(s<0) s=0;                //值为负，舍弃                    if(s>max) max=s;                }            }        }        printf("%d\n",max);    }    return 0;}