changfangti.java

实现了《算法设计与分析》的一次课后题

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

/*
 *先求出二维情形的最优值，再扩展到三维的情形；
 *MaxSun和maxsum2分别是求三维和二维的最优值函数。
 *其中对于正方体A[1:m][1:n][1:p],MaxSum先求出二维A[i][1:n][1:p](i固定时)的最优值。 
 */
public class changfangti {

	/**
	 * @param args
	 * throws IOException 
	 */
	private static int m;
	private static int n;
	private static int p;
	static int[][][] A;
    public static void main(String[] args) throws IOException {
       int i=1,j=1,k;
		try{//读入文件中的数据
			FileReader filereader=new FileReader("D:\\input.txt");
			BufferedReader reader=new BufferedReader(filereader);
			String s="";
			
			          s=reader.readLine();
				      String[] str=s.split(" ");
				      m=Integer.valueOf(str[0]);			      				     			    		    
			          n=Integer.parseInt(str[1]);			      
			          p=Integer.parseInt(str[2]);
			          A=new int[m+1][n+1][p+1];
			          while((s=reader.readLine())!=null){//用数组存储正方体中的整数
			        	  String[] str1=s.split(" ");
			        	  while((i!=m)||(j!=n+1)){
			        		  if(j==n+1){j=1;i++;}
			        	        for(k=1;k<=p;k++) 
			        		      A[i][j][k]=Integer.valueOf(str1[i-1]);
			        	      j++;			        		 
			        	  }			        	 	        	  
			        	  
			          }
		
			reader.close();
		 }catch(FileNotFoundException e){
			 System.err.println("文件没有找到！");
			 System.exit(1);
		 }
		 
		 try{        //存储计算结果到文件
			  FileWriter filewriter=new FileWriter("D:\\output.txt");//实现数据输出到文本文件
	          BufferedWriter writer=new BufferedWriter(filewriter);	 
	          int result=0;
	          result=MaxSum(m,n,p,A);
	          System.out.println(result);
	          String sresult=Integer.toString(result);
	          writer.write(sresult);
	          writer.close();
			 }catch(FileNotFoundException e)
			 {
				 File f=new File("D:\\output.txt");
				 System.exit(0);
			 }
} 
		
	
	
	public static int MaxSum(int m,int n,int p,int[][][]a){//求三维最大子长方体的大小
		
		int max,sum=0;
		int[][] b=new int[n+1][p+1];
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++)
				for(int k=1;k<=p;k++)b[j][k]=0;
			for(int t=i;t<=m;t++){
				for(int j=1;j<=n;j++)
					for(int k=1;k<=p;k++)
						b[j][k]+=a[i][j][k];
				max=maxsum2(n, p, b);
				if(max>sum)sum=max;
			}
		}
		return sum;
		
	}
	
	public static int maxsum2(int m,int n,int[][]a){//求二维矩阵的最大子矩阵
		int max,sum=0;
		int b[]=new int[n+1];
		for(int i=1;i<=m;i++){
			for(int k=1;k<=n;k++)b[k]=0;
			for(int j=i;j<=m;j++){
				for(int k=1;k<=n;k++)
					b[k]+=a[j][k];
				    max=maxsum1(n,b);
				    if(max>sum)sum=max;
			}
		}
		return sum;
		
	}

	private static int maxsum1(int n, int[] a) {//求一维最大子段和
		
		int b=0,sum=0;
		for(int i=1;i<=n;i++){
			if(b>0)b+=a[i];
			else b=a[i];
			if(b>sum)sum=b;
		}
		return sum;
	}

}