给一个n^2矩阵 求一个和最大的子矩阵

先预处理行或者列的和 然后很好的转化成一维dp

这里我的 mp[i][j] 表示i行前j个数的和

dp的过程就是 枚举列的首尾

这样 相当于把每一行当成一个数 dp求最大和 就是一个简单的问题了

#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64

int mp[105][105];

int main()
{
    int n,a,i,j,k,tmp,ans;
    while(~scanf("%d",&n))
    {
        memset(mp,0,sizeof mp);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%d",&a);
                mp[i][j]=(a+mp[i][j-1]);
            }
        ans=-99999999;
        for(i=1;i<=n;i++)//起始列
        {
            for(j=i;j<=n;j++)//结束列
            {
                for(tmp=0,k=1;k<=n;k++)//枚举高度
                {
                    if(tmp<0) tmp=0;
                    tmp+=(mp[k][j]-mp[k][i-1]);
                    if(tmp>ans) ans=tmp;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

深入理解SEAndroid（第一部分）