最大长方体问题

8601 最大长方体问题
时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0
语言: not limited
描述
一个长,宽,高分别是m,n,p的长方体被分割成m*n*p个小立方体。每个小立方体内含一个整数。试着设计一个算法，计算所给长方体的最大子长方体。子长方体的大小由它内部所含所有整数之和确定。 约定：当该长方体所有元素均为负数时,输出最大子长方体为0。
输入格式
第一行3个正整数m,n,p，其中 1<=m,n,p<=50 接下来的m*n行中每行p个整数，表示小立方体中的数。
输出格式
第一行中的数是计算出的最大子长方体的大小。
输入样例
3 3 3 0 -1 2 1 2 2 1 1 -2 -2 -1 -1 -3 3 -2 -2 -3 1 -2 3 3 0 1 3 2 1 -3
输出样例
14
21
Hint
1，先编写一维的“最大字段和”的解法。
2，基于“最大字段和”，编写二维的“最大子矩阵和”的解法。
3，基于“最大子矩阵和”，编写三维的“最大子长方体和”的解法。

22

-------------------------------------------------------------------------

8601最大长方体问题（动态规划）

#include<iostream>

usingnamespacestd;

intMaxSum(intn,int*a)

{

intsum=0;

intb=0,i;

for(i=1;i<=n;i++){

if(b>0)b+=a[i];

elseb=a[i];

if(b>sum)sum=b;

}

returnsum;

}

intMaxSum2(intm,intn,int**a)

{

intsum=0,i,j,k;

int*b=newint[n+1];

for(i=1;i<=m;i++){

for(k=1;k<=n;k++)b[k]=0;

for(j=i;j<=m;j++){

for(k=1;k<=n;k++)b[k]+=a[j][k];

intmax=MaxSum(n,b);

if(max>sum)sum=max;

}

}

returnsum;

}

intMaxSum3(intm,intn,intp,int***a)

{

intsum=0,i,j,k,l;

int**c=newint*[n+1];

for(i=1;i<=n;i++)

c[i]=newint[p+1];

for(i=1;i<=m;i++){

for(j=1;j<=n;j++)

for(k=1;k<=p;k++)

c[j][k]=0;

for(l=i;l<=m;l++){

for(j=1;j<=n;j++)

for(k=1;k<=p;k++)

c[j][k]+=a[l][j][k];

intmax=MaxSum2(n,p,c);

if(max>sum)sum=max;

}

}

returnsum;

}

intmain()

{

intsum,m,n,p,i,j,k,***a;

scanf("%d%d%d",&m,&n,&p);

a=(int***)malloc((m+1)*sizeof(int**));

for(i=1;i<=m;i++)

a[i]=(int**)malloc((n+1)*sizeof(int*));

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

a[i][j]=(int*)malloc((p+1)*sizeof(int));

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

for(k=1;k<=p;k++)

scanf("%d",&a[i][j][k]);

sum=MaxSum3(m,n,p,a);

cout<<sum<<endl;

return0;

}