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

编程之美-子数组的最大和(二维)

发表于: 2012-08-05   作者:bylijinnan   来源:转载   浏览:
摘要: package beautyOfCoding; import java.util.Arrays; import java.util.Random; public class MaxSubArraySum2 { /** * 编程之美 子数组之和的最大值(二维) */ private static final int ROW = 5; private stat
package beautyOfCoding;

import java.util.Arrays;
import java.util.Random;

public class MaxSubArraySum2 {

	/**
	 * 编程之美 子数组之和的最大值(二维)
	 */
	private static final int ROW = 5;
	private static final int COL = 6;
	private static final int MAX = 127;
	private boolean invalidInput = false;
	private static int[] source;	//[-127,127]共127*2+1个数
	static {
		int n = MAX * 2 + 1;
		source = new int[n];
		for (int i = 0; i < n; i++) {
			source[i] = i - MAX;
		}
	}

	public static void main(String[] args) {
		//生成指定行数和列数的数组。数组元素是[-127,127]范围内的随机数
		int[][] B = new int[ROW][COL];
		int n = MAX * 2 + 1;
		Random random = new Random();
		for (int i = 0; i < ROW; i++) {
			for (int j = 0; j < COL; j++) {
				int pos = random.nextInt(n);
				int num = source[pos];
				B[i][j] =  num;
			}
			System.out.println(Arrays.toString(B[i]));
		}
		
		/*int[][] B = {
				{0, -2, -7, 0},
				{9, 2, -6, 2},
				{-4, 1, -4, 1},
				{-1, 8, 0, -2}
		};*/
		
		//方法A-全枚举
		MaxSubArraySum2 test = new MaxSubArraySum2();
		int max = test.maxSubArraySumA(B);
		if (test.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max);
		}
		//方法B-部分和
		MaxSubArraySum2 test2 = new MaxSubArraySum2();
		int max2 = test2.maxSubArraySumB(B);
		if (test2.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max2);
		}
		//方法C-转化为一维
		MaxSubArraySum2 test3 = new MaxSubArraySum2();
		int max3 = test3.maxSubArraySumB(B);
		if (test3.invalidInput) {
			System.out.println("invalid input");
		} else {
			System.out.println(max3);
		}
	}

	/**
	 * 转化为一维。
	 */
	public int maxSubArraySumC(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			for (int a = 0; a < row; a++) {
				for (int c = a; c < row; c++) {
					int[] BC = this.getBC(B, a, c);
					int oneDimension = this.maxInOneDimensionalArray(BC);
					if (max < oneDimension) {
						max = oneDimension;
					}
				}
			}
		}
		return max;
	}
	
	/**
	 * maxSubArraySumC的辅助方法。得到第a行到第c行所代表的一维数组
	 */
	public int[] getBC(int[][] B,int a,int c){
		int col=B[0].length;
		int[] BC = new int[col];
		for(int i=0;i<col;i++){
			for(int j=a;j<=c;j++){
				BC[i] += B[j][i];
			}
		}
		return BC;
	}
	
	//子数组之和的最大值-一维
	public int maxInOneDimensionalArray(int[] a){
		//略去参数检查  
        int Start=0;  
        int All=0;  
        for(int i=0,len=a.length;i<len;i++){  
            All=this.maxNum(a[i],Start+a[i],All);  
            Start=this.maxNum(a[i],a[i]+Start);     //if start<0, start=a[i]  
        } 
        return All;
	}
	
	/**
	 * 用部分和的形式。其中辅助数组PS额外多一行多一列(默认初始化为0),方便计算“部分和”的“部分和”,需仔细体会
	 * PS[i][j] 表示元素(1,1)(对应原始数组B的B[0][0])和当前元素(i,j)为顶点对的子矩阵的部分和,部分和的计算如下:
	 * PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
	 */
	public int maxSubArraySumB(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			int col = B[0].length;
			int[][] PS = new int[row+1][col+1];
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					PS[i+1][j+1] = PS[i][j+1] + PS[i+1][j ] - PS[i][j] + B[i][j];
				}
			}
			max = this.maxPSij(PS);
		}
		return max;
	}
	
	/**
	 * maxSubArraySumB的辅助方法
	 * 求“部分和”的“部分和”:求得(imin, imax, jmin, jmax)代表的矩形区域的和,即题目所求
	 */
	public int maxPSij(int[][] PS) {
		int max = Integer.MIN_VALUE;
		int row = PS.length;
		int col = PS[0].length;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				for (int m = i; m < row; m++) {
					for (int n = j; n < col; n++) {
						max = this.maxNum(max, PS[i][j], PS[m][n], 
								(PS[m][n] - PS[m][j] - PS[i][n] + PS[i][j]));
					}
				}
			}
		}
		return max;

	}

	/**
	 * 穷举法,求部分和也是用枚举,有六个for循环,复杂度相当高,不过可用于检验其他方法是否正确
	 */
	public int maxSubArraySumA(int[][] B) {
		int max = Integer.MIN_VALUE;
		if (B == null) {
			invalidInput = true;
		} else {
			int row = B.length;
			int col = B[0].length;
			for (int imin = 0; imin < row; imin++) {
				for (int imax = imin; imax < row; imax++) {
					for (int jmin = 0; jmin < col; jmin++) {
						for (int jmax = jmin; jmax < col; jmax++) {
							int tmpSum = sum(B, imin, imax, jmin, jmax);
							if (tmpSum > max) {
								max = tmpSum;
							}
						}
					}
				}
			}
		}
		return max;
	}
	
	/**
	 * maxSubArraySumA的辅助方法
	 * 枚举求得(imin, imax, jmin, jmax)代表的矩形区域的和
	 */
	public int sum(int[][] B, int imin, int imax, int jmin, int jmax) {
		int result = 0;
		for (int i = imin; i <= imax; i++) {
			for (int j = jmin; j <= jmax; j++) {
				result += B[i][j];
			}
		}
		return result;
	}

	/**
	 * 返回最大的数
	 */
	public int maxNum(int x, int... yy) {
		for (int y : yy) {
			if (x < y) {
				x = y;
			}
		}
		return x;
	}
	
}

编程之美-子数组的最大和(二维)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一个有n个整数元素(可以是负数)的一维数组,连续的子数组有很多,那连续的子数组之和的最大值是什
一个有N个整数元素的一位数组(A[0],A[1],A[2],...,A[n-1]),这个数组当然有很多子数组,那么
/* * MaxSumSubArray.cpp * * Created on: 2012-6-20 * Author: jiyiqin * * 给定一个包含正数,负
求数组子序列的最大和 一、问题描述 输入一个整形数组,数组里可以有正数或负数。数组中连续的一个
注意:当函数输入无效时,返回为0,而子数组的和也有可能为0,为了区分,设置一个全局变量标记输入
注意:当函数输入无效时,返回为0,而子数组的和也有可能为0,为了区分,设置一个全局变量标记输入
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
编程之美 2.17 数组循环移位 把一个含有N个元素的数组循环右移K位, 要求时间复杂度位O(N), 且只允许
编程之美上面提供了很好的思路,那么我就用代码实现,我这个代码实现可以循环左移和循环右移 // Per
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号