一、思路

最大子矩阵和的方法和最大字段和一样

先单独对每行求最大字段和（此时，子矩阵的行为1，就是最大字段和了）

然后，把第i行后的各行对应列的元素加到第i行的对应列元素，每加一行，就求一次最大字段和，这样就把子矩阵的多行压缩为一行了，一行了就是最大字段和了

也可以这样理解：

a11 a12 a13
a21 a22 a23
a31 a32 a33

如图，先求第一行最大子段和，再求第一行跟第二行合起来的最大子段和，如a21+a11, a22+a12, a23+a13 的最大子段和，再求第一到第三合起来的最大子段和，如a11+a21+a31, a12+a22+a32, a13+a23+a33的最大子段和…..以此类推，直到求出整个矩阵的合起来的最大子段和，求出他们之中最大的那个和就是解.

二、AC code

#include <stdio.h>
#include <stdlib.h>

int m[101][101];

int main()
{
    int n,max,i,j,k,tmp;

    while(scanf("%d",&n) != EOF)
    {
        max=-10000;
        /*
        输入时，顺便求出各行的最大字段和的最大值
        */
        for(i=0;i<n;++i)
        {
            tmp=0;
            for(j=0;j<n;++j)
            {
                scanf("%d",&m[i][j]);
                if(tmp>0)tmp+=m[i][j];
                else tmp=m[i][j];

                if(tmp>max)max=tmp;
            }
        }

        for(i=0;i<n-1;++i)
        {
            for(j=i+1;j<n;++j)
            {
                tmp=0;
                for(k=0;k<n;++k)
                {
                    //相当于把子矩阵多行压缩为一行了
                    m[i][k]+=m[j][k];
                    if(tmp>0)tmp+=m[i][k];
                    else tmp=m[i][k];

                    if(tmp>max)max=tmp;
                }
            }

        }
        printf("%d\n",max);
    }

    return 0;   
}

        

          
        
        
        

          

          AI 代码解读