最大子长方体问题.cpp

*Cube:最大子长方体问题 问题描述: 一个长

/*Cube:最大子长方体问题
问题描述:
一个长，宽，高分别为m,n,p的长方体被分割成个m*n*p个小立方体。每个小立方体内有一个整数。
求所给长方体的最大子长方体。子长方体的大小由它所含所有整数之和确定。 
*/


#include<iostream.h>
#include<fstream.h>

int m,n,p;
int ***temp;
int min=-30000;

int MaxSum(int x,int *a);
int MaxSum2(int x,int y,int **a);
int MaxSum3(int x,int y,int z,int ***a);

void main()
{
     ifstream takenum;
	 takenum.open("input.txt",ios::nocreate);
	 if(!takenum)
	 {
		 cout<<" File Error!"<<endl;
		 return;
     }
	 else
	 {
		 ofstream myout("output.txt");

			int result;
			takenum>>m;
			takenum>>n;
			takenum>>p;	 

       		temp=new int**[m+1];                     
			for (int u=1;u<=m;u++) 
			{
				temp[u]=new int*[n+1];
				for (int v=1;v<=n;v++)
					temp[u][v] = new int[p+1];
			} //动态分配三维数组.
		 
			for(int i=1;i<=m;i++)
			   for(int j=1;j<=n;j++)
				 for(int k=1;k<=p;k++)
					takenum>>temp[i][j][k];
             
			takenum.close();		 
					result=MaxSum3(m,n,p,temp);
					myout<<result<<endl;
			myout.close();
	 }//else
}//main



int MaxSum(int x,int *a)
{
	int sum=min;
	int b=0;
	for(int i=1;i<=x;i++)
	{
		if(b>0) b+=a[i];
		else b=a[i];
        if(b>sum) sum=b;
    }
  return sum;
}

int MaxSum2(int x,int y,int **a)
{
	int sum=min;
	int *b=new int[y+1];
	for(int i=1;i<=x;i++)
    {
		for(int k=1;k<=y;k++) b[k]=0;
		for(int j=i;j<=x;j++)
        {
			for(int k=1;k<=y;k++) b[k]+=a[j][k];
            int max=MaxSum(y,b);
			if(max>sum) sum=max;
        }
	}
   return sum;
}

int MaxSum3(int x,int y,int z,int ***a)
{
	int sum=min;
    int **b;
	b=new int*[y+1];
	for(int s=0;s<=y;s++)
		b[s]=new int[z+1];
	for(int i=1;i<=x;i++)
    {
		for(int u=1;u<=y;u++)
			for(int v=1;v<=z;v++)
			     b[u][v]=0;
		for(int j=i;j<=x;j++)
        {
		   for(int u=1;u<=y;u++)
			   for(int v=1;v<=z;v++)
				   b[u][v]+=a[j][u][v];
			   
		   int max=MaxSum2(y,z,b);
		   if(max>sum) sum=max;
        }
	}
  
  return sum;
}