当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-35.求一个矩阵中最大的二维矩阵 ( 元素和最大 )

发表于: 2012-01-21   作者:bylijinnan   来源:转载   浏览:
摘要: the idea is from: http://blog.csdn.net/zhanxinhang/article/details/6731134 public class MaxSubMatrix { /**see http://blog.csdn.net/zhanxinhang/article/details/6731134 * Q35 求一个矩阵中最大的二维
the idea is from: http://blog.csdn.net/zhanxinhang/article/details/6731134

public class MaxSubMatrix {

	/**see http://blog.csdn.net/zhanxinhang/article/details/6731134
	 * Q35
求一个矩阵中最大的二维矩阵 ( 元素和最大 ). 如 :
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是 :
4 5
5 3
three solutions:
1.brutalFind:calculate all the possible sum and find the largest
2.verticalFind:when matrix's rowIndex is larger than columnIndex,like "int[][] b" in the following code
3.herizonalFind:when matrix's rowIndex is smaller than columnIndex,like "int[][] a" in the following code
both 2 and 3 avoid duplicate calculation
	 */
	public static void main(String[] args) {
		MaxSubMatrix msm=new MaxSubMatrix();
		int[][] a={
				{2,3,4},
		        {1,3,3},
		        {1,4,6},
		        {1,4,8},
		        {2,3,2},
		};
		int[][] b={
				{1, 2, 0, 3, 4},
		        {2, 3, 4, 5, 1},
		        {1, 1, 5, 3, 0},
		};
		
		int[][] result=msm.findSumMaxSubMatrix(a);
		msm.printArray(result);
		System.out.println("----------------");
		result=msm.brutalFind(a);
		msm.printArray(result);
		System.out.println("----------------");
		
		result=msm.findSumMaxSubMatrix(b);
		msm.printArray(result);
		System.out.println("----------------");
		result=msm.brutalFind(b);
		msm.printArray(result);
	}
	
	public int[][] findSumMaxSubMatrix(int[][] a){
		int[][] result=null;
		int row=a.length;
		int col=a[0].length;
		if(row>=col){
			result=herizonalFind(a,row,col);
		}else{
			result=verticalFind(a,row,col);
		}
		return result;
	}
	
	public int[][] brutalFind(int[][] a){
		int[][] result=new int[2][2];
		int row=a.length;
		int col=a[0].length;
		int sum=0;
		int p=0;
		int q=0;
		for(int i=0;i<row-1;i++){
			for(int j=0;j<col-1;j++){
				int x=a[i][j];
				int y=a[i][j+1];
				int z=a[i+1][j];
				int k=a[i+1][j+1];
				int temp=x+y+z+k;
				if(temp>sum){
					sum=temp;
					p=i;
					q=j;
				}
			}
		}
		result[0][0]=a[p][q];
		result[0][1]=a[p][q+1];
		result[1][0]=a[p+1][q];
		result[1][1]=a[p+1][q+1];
		return result;
	}
	
	public int[][] herizonalFind(int[][] a,int row,int col){
		int[][] result=new int[2][2];
		int lastHerizonalSum=a[0][0]+a[0][1];
		int sum=0;
		int p=0;
		int q=0;
		for(int i=1;i<row;i++){
			for(int j=0;j<col-1;j++){
				int temp=lastHerizonalSum+a[i][j]+a[i][j+1];
				lastHerizonalSum=a[i][j]+a[i][j+1];
				if(temp>sum){
					sum=temp;
					p=i;
					q=j;
				}
			}
		}
		result[0][0]=a[p-1][q];
		result[0][1]=a[p-1][q+1];
		result[1][0]=a[p][q];
		result[1][1]=a[p][q+1];
		return result;
	}
	
	public int[][] verticalFind(int[][] a,int row,int col){
		int[][] result=new int[2][2];
		int lastVerticalSum=a[0][0]+a[1][0];
		int sum=0;
		int p=0;
		int q=0;
		for(int i=0;i<row-1;i++){
			for(int j=1;j<col;j++){
				int temp=lastVerticalSum+a[i][j]+a[i+1][j];
				lastVerticalSum=a[i][j]+a[i+1][j];
				if(temp>sum){
					sum=temp;
					p=i;
					q=j;
				}
			}
		}
		result[0][0]=a[p][q-1];
		result[0][1]=a[p][q];
		result[1][0]=a[p+1][q-1];
		result[1][1]=a[p+1][q];
		return result;
	}
	
	public void printArray(int[][] a){
		int row=a.length;
		int col=a[0].length;
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				System.out.print(a[i][j]+" ");
			}
			System.out.println();
		}
	}
}

java-35.求一个矩阵中最大的二维矩阵 ( 元素和最大 )

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
转载:http://blog.csdn.net/zhanxinhang/article/details/6731134 题:求一个矩阵中最大的n==2的二
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
上篇讲了一维的连续子数组和的最大值(编程之美错误分析),下面来分析二维数组的最大子数组和,亦
<以下微软面试题全来自网络> <以下答案与分析纯属个人观点,不足之处,还望不吝指出^_^>
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
转载自http://blog.csdn.net/zhanxinhang,作者:花心龟的扮演者ZhanHang <span style="color:#99
题目:n*n的矩阵,每个格一个数,一个人从(0,0)走到(n,n),只能向右或者向下走,问怎么走,经
/* (程序头部注释开始) * 程序的版权和版本声明部分 * Copyright (c) 2011, 烟台大学计算机学院学生
#include <iostream> #include <iomanip> using namespace std; int main() { int a[3]
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号