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

编程之美-子数组的最大乘积

发表于: 2012-08-06   作者:bylijinnan   来源:转载   浏览:
摘要: public class MaxProduct { /** * 编程之美 子数组的最大乘积 * 题目: 给定一个长度为N的整数数组,只允许使用乘法,不能用除法,计算任意N-1个数的组合中乘积中最大的一组,并写出算法的时间复杂度。 * 以下程序对应书上两种方法,求得“乘积中最大的一组”的乘积——都是有溢出的可能的。 * 但按题目的意思,是要求得这个子数组,而不

public class MaxProduct {

	/**
	 * 编程之美 子数组的最大乘积
	 * 题目: 给定一个长度为N的整数数组,只允许使用乘法,不能用除法,计算任意N-1个数的组合中乘积中最大的一组,并写出算法的时间复杂度。
	 * 以下程序对应书上两种方法,求得“乘积中最大的一组”的乘积——都是有溢出的可能的。
	 * 但按题目的意思,是要求得这个子数组,而不是这个子数组的乘积。
	 * 实际应用中,返回去掉的那一个元素的下标更合理。
	 */

	private boolean invalidInput = false;

	public static void main(String[] args) {
		int[][] aa = { 
						{ 0, 0, 1, 2 }, 
						{ 0, 1, 2 }, 
						{ 0, -1, 2 },
						{ -1, -2, -3 }, 
						{ 1, 2, 3 }, 
					};
		for (int[] a : aa) {
			MaxProduct m = new MaxProduct();
			int result = m.maxProductA(a);
			int result2 = m.maxProductB(a);
			if (m.invalidInput) {
				System.out.println("invalid input!");
			} else {
				System.out.println(result + "," + result2);
			}
		}
	}

	// 对应书上的解法1.空间换时间
	public int maxProductA(int[] a) {
		if (a == null || a.length == 0) {
			invalidInput = true;
			return 0;
		}
		int n = a.length;
		int[] s = new int[n];
		s[0] = 1;
		for (int i = 1; i <= n - 1; i++) {
			s[i] = s[i - 1] * a[i - 1];
		}
		int[] t = new int[n];
		t[n - 1] = 1;
		for (int i = n - 2; i >= 0; i--) {
			t[i] = t[i + 1] * a[i + 1];
		}
		int p = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			int pi = s[i] * t[i];
			if (pi > p) {
				p = pi;
			}
		}
		return p;
	}

	/*
	 对应书上的解法2。对乘积作分类讨论。书上的分析如下:
	 计算N个数的乘积为P,然后分P的正负性讨论如下:
     1,P==0
             说明P中必定至少含有一个0。假设将这个0去掉后得到N-1个元素的乘积为Q。
           1.1 Q==0
                  返回0。说明N个元素中必有至少两个0,所以不管去掉什么元素,N-1个乘积必为0。
           1.2 Q为正
                  返回Q。说明其中再无0了,若之前去掉的不是0,则剩余的N-1个的乘积必为0。小于现在的Q。
           1.3 Q为负
                  返回0,。说明其中再无0了,若之前去掉的不是0,则剩余的N-1个的乘积必为0。大于现在的Q,取大者,所以之前应该保留0。
    2,P为负
          说明这N个数中无0,并且至少有一个负数。所以只有去掉一个绝对值最小的负数才获得最大乘积Q。并且这个负数必定是存在的。
    3,P为正
          由于可能负负得正,所以现在应该考虑到应该去掉一个绝对值最小的正数,但是这个正数不一定存在,比如数组-1,-1。所以如果该正数不存在,就应该去掉一个绝对值最大的负数。
		 同时注意,为了避免乘积溢出,建议只统计符号,计算0,正,负的个数 。  
	 */
	public int maxProductB(int[] a) {
		if (a == null || a.length == 0) {
			invalidInput = true;
			return 0;
		}
		int n = a.length;
		int zeroCount = 0;
		int negativeCount = 0;
		int positiveCount = 0;
		int maxNegative = Integer.MIN_VALUE; // 最大的负整数是-1,初始化应该设为最小的负整数
		int minNegative = -1; // 最小的负整数是Integer.MIN_VALUE.,初始化应该设为最大的负整数
		int minPositive = Integer.MAX_VALUE; // 最小的正整数,初始化为最大的正整数

		for (int i : a) {
			if (i == 0) {
				zeroCount++;
			}
			if (i > 0) {
				positiveCount++;
				if (minPositive > i) {
					minPositive = i;
				}
			}
			if (i < 0) {
				negativeCount++;
				if (maxNegative < i) {
					maxNegative = i;
				}
				if (minNegative > i) {
					minNegative = i;
				}
			}
		}

		// 设P为数组所有元素的乘积。Q为除去一个0元素之外其他元素的乘积。
		int p = 1;
		int excludeItem = 0;
		// P=0
		if (zeroCount >= 2) { // 有两个或两个以上的0
			p = 0;
		} else if (zeroCount == 1) { // 有一个0
			if (negativeCount % 2 == 0) { // Q>0
				excludeItem = 0;
			} else { // Q<0
				p = 0;
			}
		} else {
			// P>0
			if (negativeCount % 2 == 0) {
				if (positiveCount > 0) {
					excludeItem = minPositive;
				} else {
					excludeItem = minNegative;
				}
				//P<0
			} else {
				excludeItem = maxNegative;
			}
		}
		if (p != 0) {
			for (int i = 0; i < n; i++) {
				if (excludeItem != a[i]) {
					p *= a[i];
				}
			}
		}

		return p;
	}

}

编程之美-子数组的最大乘积

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一个有N个整数元素的一位数组(A[0],A[1],A[2],...,A[n-1]),这个数组当然有很多子数组,那么
问:有很多个无序的数,我们姑且假定它们各不相等,怎么选出其中最大的若干个数呢? 答:可以这样写
还好看到了,这个以前好早见到过。 用得是辗转相除法。 k =x/y b=x%y 则 x = ky+b 如果一个整数能够
题目 给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合乘积中的最
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
编程之美 2.17 数组循环移位 把一个含有N个元素的数组循环右移K位, 要求时间复杂度位O(N), 且只允许
编程之美上面提供了很好的思路,那么我就用代码实现,我这个代码实现可以循环左移和循环右移 // Per
题目:如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两节点
题目描述:输入n个整数,输出其中最大的k个。 举例:输入序列1、2、3、4、5、6、7、8,输出最大的4
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号