hdu1081 最大子矩陣

hdu1081 最大子矩陣

最大子矩陣自然直在最大連續子序列的升級版 不過其原理都是用到了動態規劃思想 只是矩陣用到了枚舉 +合並 把很多列看成是一列的和

#include
#include
#include
using namespace std;
#define INF -10000000

int n,num[110][110],mark[110];
int linemax()
{
    int x=0,i,Max=INF;
    for(i=1;i<=n;i++)
    {
        if(x>0)
        {
            x+=mark[i];
        }
        else x=mark[i];
        if(x>Max) Max=x;
    }
    return Max;
}
int rowmax()
{
    int i,j,k;
    int Max=INF;
    for(i=1;i<=n;i++)//枚舉所有行
    {
        memset(mark,0,sizeof(mark));
        for(j=i;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                mark[k]+=num[j][k]; //列向求和   
                
            }
            int x=linemax();//最大連續子序列求法求出最大值
            if(x>Max) Max=x;
        }
        
    }
    return Max;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        scanf("%d",&num[i][j]);
        printf("%d\n",rowmax());
    }
    return 0;
}