[摆个擂台]设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积

Question

这是一个Google笔试题，我5年前看到的。

设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积。

例如：输入数组[2,4,5,3]；则返回60，（对应的N-1个元素是[3,4,5]，它比[2,3,4],[2,3,5],[2,4,5]三种组合的乘积都大）。

要求：
1. 时间复杂度尽可能低
2. 不可使用任何PHP自带的数组函数，能使用if, for, switch这样的控制结构，和isset/is_array/is_int这样的基本类型检查函数

函数模板：

<?php
class NumUtil
{
	 /**
	 * @param array  $arr
	 * @return integer
	 */
	static public function findMaxProd(){/*你的代码*/}
}

分割线

单元测试我写好了，敢上擂台的同学，把代码贴到下面，我来检查能通过几个单元测试，哈哈。

挑擂结果（有两个测试用例我只占了个位，没写具体的数据。下面的结果都不包含这两个用例）

updated @ 2013-3-22 16:32

JoyQi 目前最接近标准答案的，只有2个测试用例没通过，时间复杂度，我目测是没到最小，但跟我写的也不相伯仲，如果用C语言来实现，是循环更耗费时间还是大数相除更耗费时间就不好说了。

Sunyanzi 的还差三个测试用例没通过

公布答案了：单元测试

/**
 * 函数名释义：
 * az: Amount of Zero, 零的个数
 * ap: Amount of Positive, 正整数个数
 * an: Amount of Negative, 负数个数
 *
 * gt: Greater Than, 大于
 * eq: Equal, 等于
 * lt: Less Than, 小于
 *
 * o: odd, 奇数
 * e: even, 偶数
 *
 * #################### MECE Tree ####################
 *参数输入正确的正常流程
 * 	零的个数大于1			@see TestCaseNumUtil::test_amountOfZeroGreaterThanOne()
 * 	零的个数等于1
 *		负数个数为偶数
 *			有正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
 * 			无正数	   @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
 * 		负数个数为奇数
 * 			有正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
 *			无正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
 * 	零的个数小于1
 *		负数个数为偶数
 *			有正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
 * 			无正数	   @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
 * 		负数个数为奇数
 * 			有正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
 *			无正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
 *
 *参数输入错误的异常流
 *	输入的参数不是数组		@see TestCaseNumUtil::test_inputIsNotArray()
 * 	是个数组
 * 		元素个数小于2个	@see TestCaseNumUtil::test_ArrayContainLessThanTwoInteger()
 *		元素多于2个
 * 			不全是整数	@see TestCaseNumUtil::test_ArrayContainNonInteger()
 *
 *白盒测试
 *	元素个数超过int型上限 @see TestCaseNumUtil::test_amountOfZeroGreaterThanMaxInt()
 *	元素的乘积超过PHP上限	@see TestCaseNumUtil::test_prodGreaterThanMaxInt()
 *
 * #################### MECE Tree ####################
 */
class TestCaseNumUtil extends PHPUnit_Framework_TestCase
{
	/**
	 * 零的个数大于1
	 * 本来根据根据负数个数奇偶性、正数有无可以分成四种情况
	 * 但这四种情况明显可以归并到这一种，因此不再分成四个条件来写
	 */
	public function test_amountOfZeroGreaterThanOne()
	{
		$arr = array_merge(
			$this->produceIntArray(rand(2, 10), self::INT_SIGN_ZERO),
			$this->produceIntArray(rand(10, 20), self::INT_SIGN_RAND)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数等于1 偶数个负数 有正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
	{
		$this->execTest(200, array(0, -1, -2, 10, 5, 2));
	}

	/**
	 * 零的个数等于1 偶数个负数 无正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
	{
		$this->execTest(100, array(0, -1, -2, -10, -5));
	}

	/**
	 * 零的个数等于1 奇数个负数 有正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
	{
		$arr = array_merge(
			$this->produceIntArray(11, self::INT_SIGN_NEGA),
			array(0),
			$this->produceIntArray(rand(1,10), self::INT_SIGN_POSI)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数等于1 奇数个负数 无正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
	{
		$arr = array_merge(
			$this->produceIntArray(11, self::INT_SIGN_NEGA),
			array(0)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数小于1 偶数个负数 有正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
	{
		$this->execTest(100, array( -1, -2, -10, -5, 10));
	}

	/**
	 * 零的个数小于1 偶数个负数 无正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
	{
		$this->execTest(-10, array( -1, -2, -1024, -5));
	}

	/**
	 * 零的个数小于1 奇数个负数 有正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
	{
		$this->execTest(200, array(-2, -10, -5, 4), self::INT_SIGN_POSI);
	}

	/**
	 * 零的个数小于1 奇数个负数 无正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
	{
		$this->execTest(50, array(-2, -10, -5), self::INT_SIGN_POSI);
	}

	public function test_inputIsNotArrayDataProvider()
	{
		return array(
			array(NULL),
			array(TRUE),
			array(1024),
			array(3.14),
			array("not an array"),
			array(new TestCaseNumUtil),
		);
	}

	/**
	 * 输入的参数不是数组
	 * @dataProvider test_inputIsNotArrayDataProvider
	 * @expectedException PHPUnit_Framework_Error
	 */
	public function test_inputIsNotArray($arg)
	{
		NumUtil::findMaxProd($arg);
	}

	/**
	 * 数组元素个数小于2个
	 */
	public function test_ArrayContainLessThanTwoInteger()
	{
		$this->assertFalse(NumUtil::findMaxProd(array(10)));
	}

	/**
	 * 数组元素不全是整数
	 */
	public function test_ArrayContainNonInteger()
	{
		$this->assertFalse(NumUtil::findMaxProd(array(-2, TRUE, -5)));
	}

	/**
	 * 如果代码中用整形来记录【零、正数、负数】的个数，输入的数组元素个数超过int型上限，就会造成数据溢出
	 */
	public function test_amountOfZeroGreaterThanMaxInt()
	{
		//这种极端情况不支持，也不测试，写在这里仅仅表示我考虑到这点了
	}

	/**
	 * N-1个元素的乘积超过PHP能表达的上限，就会造成数据溢出
	 */
	public function test_prodGreaterThanMaxInt()
	{
		//这种情况暂时不支持，也不测试，写在这里仅仅表示我考虑到这点了
	}

	const INT_SIGN_POSI = "positive";
	const INT_SIGN_NEGA = "negative";
	const INT_SIGN_ZERO = "zero";
	const INT_SIGN_RAND = "RAND";

	private function  produceIntArray($length, $sign)
	{
		$int_arr = array();
		switch($sign)
		{
			case self::INT_SIGN_POSI :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = rand(1, 99);
				}
				break;
			case self::INT_SIGN_NEGA :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = 0 - rand(1, 99);
				}
				break;
			case self::INT_SIGN_ZERO :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = 0;
				}
				break;
			case self::INT_SIGN_RAND :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = $i % 2 ? rand(1, 99) : 0 - rand(0, 99);
				}
				break;
		}
		return $int_arr;
	}

	private function execTest($exp, array $arr, $sign = self::INT_SIGN_NEGA)
	{
		$randInt = self::INT_SIGN_POSI == $sign ? rand(1, 100) : 0 - rand(1, 99);
		$arr[] = $randInt;
		$arr[] = $randInt;
		shuffle($arr);
		$this->assertEquals($exp * $randInt * $randInt, NumUtil::findMaxProd($arr));
	}
}

公布答案了：我的函数实现

class NumUtil
{
	/**
	 * @param array $arr
	 * @return integer
	 */
	static public function findMaxProd(array $arr)
	{

		$arr_len = count($arr);
		if (2 > $arr_len)
		{
			return false;
		}

		/*
		 * 先遍历数组找出零、负数、正数的数量
		 * 只做统计，不排序，不做乘法
		 */
		$amount_zero = 0;//零的个数
		$amount_negative = 0;//负数个数
		$amount_positive = 0;//正数个数
		$min_positive_index = null;
		$min_negative_index = null;
		$max_negative_index = null;
		$the_only_zero_index = null;

		for($i = 0; $i < $arr_len; $i++)
		{
			if (!is_int($arr[$i]))
			{
				return false;
			}
			if (0 > $arr[$i])
			{
				$amount_negative += 1;
				if (is_null($min_negative_index) || $arr[$i] < $arr[$min_negative_index])
				{
					$min_negative_index = $i;
				}
				if (is_null($max_negative_index) || $arr[$i] > $arr[$max_negative_index])
				{
					$max_negative_index = $i;
				}
			}
			else if (0 == $arr[$i])
			{
				$amount_zero += 1;
				$the_only_zero_index = $i;
			}
			else
			{
				$amount_positive += 1;
				if (is_null($min_positive_index) || $arr[$i] < $arr[$min_positive_index])
				{
					$min_positive_index = $i;
				}
			}
		}

		/**
		 * Logical control start
		 */
		if (1 < $amount_zero)
		{
			/*
			 * 0的个数大于1，任意取N-1个元素，其乘积都是0
			 * 故无须再判断正数和负数的个数
			 */
			return 0;
		}
		else if (1 == $amount_zero)
		{
			if (1 == $amount_negative % 2)
			{//奇数个负数
				/*
				 * 最大乘积只能是0，无需判断正数个数
				 */
				return 0;
			} else {//偶数个负数
				/*
				 * 除0之外的N-1个整数乘积最大
				 */
				$pick_out_index = $the_only_zero_index;
			}
		}
		else// if (1 > $amount_zero)
		{
			if (1 == $amount_negative % 2)//奇数个负数
			{
				/*
				 * 除【绝对值最小的负数】之外的N-1个整数乘积最大
				 */
				$pick_out_index = $max_negative_index;
			}
			else//偶数个负数
			{
				if (0 < $amount_positive)
				{//存在正数
					/*
					 * 除【绝对值最小的正数】之外的N-1个整数乘积最大
					 */
					$pick_out_index = $min_positive_index;
				}
				else
				{
					/*
					 * 除【绝对值最大的负数】之外的N-1个整数乘积最大
					 * 乘积为负
					 */
					$pick_out_index = $min_negative_index;
				}
			}
		}

		/**
		 * 若需要计算N-1个元素的乘积
		 */
		$prod = 1;
		for($i = 0; $i < $arr_len; $i++)
		{
			if ($i != $pick_out_index)
			{
				$prod *= $arr[$i];
			}
		}
		return $prod;
	}
}

几点说明：

1. 这是我做《如何设计完备可靠的测试用例》培训用的一个代码示范，在github上开源的：https://github.com/qinjx/lotusphp/blo...，会持续更新，敬请关注
2. 我贴出来的测试用例只有“参数输入正确的正常流程”是100%做到了MECE（完全穷尽，彼此独立），“参数输入错误的异常流”还没做到MECE，极端情况的“白盒测试”就更谈不上MECE了，而且也没写测试方法体

Answer 1

php写代码太难受，我就不写了，主要要注意的几个点供参考：

1. 积可能会很大，要用大整数乘法。即使如此，大整数和一个int直接乘也可能会溢出，所以int也要先转换成一个大整数。php的整数底层是（有符号）long存的，32bit和64bit的最大数情况不一样，题目没有明确，保守点吧。

2. 会有0，两个以上的0结果直接返回0; 1个0和偶数个负数、无正数的情况也可以直接返回0。

3. 会有负数，要分别考虑奇数/偶数个负数的情况，分别考虑应该删掉绝对值最小的负数/正数。

4. 如果有偶数个负数的话，应当删除绝对值最大的负数。

后三个的逻辑（也许还有漏掉的情况）可以用暴力简化一下，把输入分成正数、零、负数三类，分别去掉1个零、最大的正数、最小的正数、最大的负数、最小的负数（最多去掉N个, N<=5）算出结果，然后再分别乘以那N个中的任意N-1个，比较一下结果，然后输出最大的就行了，这个效率也足够高。

想想还是写了个python的版本，我估计应该可以通过绝大部分测试了，比php写起来真是舒服太多了。

#!/usr/bin/python

def pop_min_max(l):
    if len(l) == 0:
        return []

    max_item = max(l)
    min_item = min(l)

    l.remove(max_item)

    if max_item == min_item:
        return [max_item]
    else:
        l.remove(min_item)
        return [max_item, min_item]


def findMaxProd(nums):
    if not isinstance(nums, list) or len(nums) == 0:
        raise Exception('bad input')

    if len(nums) == 1:
        return 1

    positive = filter(lambda x: x > 0, nums)
    negtive  = filter(lambda x: x < 0, nums)
    n_zero   = len(nums) - len(positive) - len(negtive)

    if n_zero > 1:
        return 0

    check_list = pop_min_max(positive) + pop_min_max(negtive)
    if n_zero:
        n_zero -= 1
        check_list = [0] + check_list

    pre_ans = reduce(lambda a, b: a * b, [0] * n_zero + positive + negtive, 1)

    ans = []
    for i in check_list:
        ans.append(reduce(lambda a, b: a * b, filter(lambda x: x != i, check_list), pre_ans))
    return max(ans)

print findMaxProd([2, 3, -1, -2, -3])

测试结果

根据题主的单元测试输出了一组测试用例，结果是有两组没通过（最后两组），其中一个是[10]这样的情况，我认为0个数相乘应该返回1（类似于x的0次方=1，这个见仁见智，不能算错吧），另一个是没有考虑数组中出现非int的情况。

由于python原生支持大整数运算，所以如果测试中出现超过int的数据，这代码应当也能顺便做对。

tests = [ 
    (0, [0,0,0,0,0,0,0,-38,8,-28,86,-12,93,-3,3,-74,81,-57]), 
    (39200, [-1,-14,2,5,-14,0,10,-2]), 
    (62500, [-5,-2,0,-1,-25,-25,-10]), 
    (0, [-5,-21,-35,-64,-36,-72,-71,-64,-59,-83,-58,0,86,33,44,43,46,81,87]), 
    (0, [-50,-23,-60,-68,-72,-84,-16,-66,-50,-54,-74,0]), 
    (324900, [-10,-2,-5,-1,-57,-57,10]), 
    (-86490, [-1,-1024,-93,-5,-2,-93]), 
    (819200, [64,-5,4,-2,-10,64]), 
    (451250, [-5,-2,95,-10,95]), 
    (None, [10]), 
    (None, [-2,True,-5]), 
]

for answer, arr in tests:
    if answer != findMaxProd(arr):
        print 'failed for:', str(arr)

运行测试输出

failed for: [10]
failed for: [-2, True, -5]

Answer 2

直接上code

class NumUtil
{
    /**
     * @param array  $arr
     * @return integer
     */
    static public function findMaxProd(array $arr)
    {
        if (empty($arr)) {
            return 0;
        }

        $result = 1;
        $minPlus = NULL;
        $minMinus = NULL;
        $maxMinus = NULL;
        $zeroCount = 0;
        $nZeroCount = 0;

        foreach ($arr as $num) {
            if ($num > 0) {
                if (NULL === $minPlus || $num < $minPlus) {
                    $minPlus = $num;
                }

                $result *= $num;
                $nZeroCount ++;
            } else if ($num < 0) {
                if (NULL === $minMinus || $num < $minMinus) {
                    $minMinus = $num;
                }
                
                if (NULL === $maxMinus || $num > $maxMinus) {
                    $maxMinus = $num;
                }

                $result *= $num;
                $nZeroCount ++;
            } else {
                $zeroCount ++;
            }
        }

        // 有0的情况
        if ($zeroCount > 1) {
            return 0;
        } else if (1 == $zeroCount) {
            return $result > 0 && $nZeroCount > 0 ? $result : 0;
        }

        // 没0的情况
        switch (true) {
            case $result > 0 && NULL !== $minPlus:
                return $result / $minPlus;
            case $result > 0 && NULL === $minPlus:
                return $result / $minMinus;
            case $result < 0:
                return $result / $maxMinus;
            default:
                break;
        }

        return 0;
    }
}

Answer 3

不写代码了，直接上逻辑，既然是n-1，意思就是踢掉一个即可，那么
对数组循环一遍，求以下值：
1.小于0的最大负数max
2.大于等于0的最小非负整数min
3.小于0的元素的个数n

然后，判断:
1. 如果 n== 0，则直接踢掉min
2. 如果 n > 0，则：

• 1. 如果 n 为偶数，则裁掉 min
• 2. 如果 n 为奇数, 如果min=0裁掉min，否则裁掉 max

如果是绝对值最大：则
比较 min 与 max ，谁的绝对值小，裁掉谁，另外也不用统计n了

两次foreach ,一次用于查找条件，第二次用于裁掉元素

算法复杂度 2n ~ O(n)

Answer 4

实际上应该是个排序题吧，先取绝对值排序，再根据 0 和负数出现的情况直接算最大乘积。没必要把所有乘积都算一遍的。先记上记号，回头补作业。

Answer 5

首先一个事情是问题里 isset 写错了 ... 不过这不是大问题啦 ...

上午看到这个问题的时候就准备写下 ... 然后看了别人回复里描述的算法发现完全理解不能 ...

觉得自己好蠢 ... 想来想去觉得连算法都看不懂的话 ... 还是不丢人现眼的好 ...

中午吃完饭晒太阳 ... 突然觉得声望什么的都是浮云 ... 不犯错永远不会提高 ...

再说吃完饭不活动一下会胖 ... 所以还是写了 ... 毕竟输不丢人 ... 怕才丢人 ...

我的算法停留在小学生水平 ... 只会用最简单最笨的方法 ...

代码如下 ... 欢迎嘲笑 ...

<?php
//----------------------------------------------------------
// * Challenge Accepted
//----------------------------------------------------------
class NumUtil
{
    /**
     * the function template
     *
     * @version  0.1.0 2013.03.22
     * @since    0.1.0 2013.03.22
     * @author   Sunyanzi <[e-mail]>
     * @param    $arr     the input array
     * @return   integer  biggest product or 0 when error
     * @static
     * @access   public
     */
    static public function findMaxProd( array $arr ) {

        /* you give me nothing ..? */
        if ( count( $arr ) < 2 ) return 0;

        /* initialize some variables ... null means infinitesimal ... */
        $positive = $negative = null;
        $zero = $minimum = 0;
        $result = 1;

        /* let go though numbers ... */
        foreach( $arr as $number ) {

            /* only integer accepted ... */
            if ( ! is_int( $number ) ) return 0;

            /* BC is useless becase we have to return an integer  ... */
            if ( 0 !== $number ) $result *= $number;

            /* is this number the smallest positive ... */
            if ( 0 < $number && $number < $positive ) 
                $positive = $number;

            /* or the biggest negative ..? */
            elseif ( 0 > $number && $number > $negative ) 
                $negative = $number;

            /* or the smallest nagative ..? */
            elseif ( $minimum > $number )
                $minimum = $number;

            /* go off work when more than one zero appears ... */
            elseif ( 0 === $number && ++ $zero > 1 ) return 0; 

        }

        /* almost there ... is there an nuisance in us ..? */
        if ( 0 === $zero ) {

            /* where are you hide from us ..? */
            $nuisance = ( $result > 0 ) ? 'positive' : 'negative';

            /* not caught ya ..? impossible ... */
            if ( is_null( $$nuisance ) ) $nuisance = 'minimum';

            /* good bye kid ... we dun need you ... */
            if ( 0 === $zero ) $result /= $$nuisance;

        }

        /* done ... but wait a moment ... we need an interger right ..? */
        return is_int( $result ) ? $result : 0; 
        
    }

}

我知道肯定会有各种各样的地方会出问题 ... 不想写测试了 ... 就扔在这里吧 ...

限制了传入数组中的每一个元素都必须是整形 ... 数组不规范返回 0 ... 数组元素个数不够返回 0 ...

题目中限制了传出是整形 ... 所以如果计算结果大于 PHP_INT_MAX 返回 0 ...

就是这样 ... 请测试 ... 我有不及格的心理准备了恩恩 ...

Answer 6

写个python的吧..

def find_max(input):
  if len(input) < 2:
     return input
  max = 1
  for i in input:
    max = max*i
  
  result = None

  for i in input:
    _ = max/i
    if result and _ > result:
      result = _
    else: 
      result = _
    
   return result
  

Answer 7

不会写php的。。。就说一下我的思想
既然求n-1个元素的最大乘积，那么只要踢出一个元素即可
考虑数组元素所属集合为实数集，分情况讨论
首先，如果0元素超过一个，那么结果就肯定是0
其次，接下来的情况分开讨论
1.数组中有奇数个值为负数的元素
遍历一遍数组，
如果不包含0元素，那么剔除掉绝对值最小的负数
如果包含一个0元素，随便剔除除0以外的任何元素
2.数组中有偶数个值为负数的元素
遍历一遍数组
如果不包含0元素，那么剔除绝对值最小的正数
如果包含一个0元素，剔除0元素
`

double function(double[] array){
int negativeMin,zeroPostion,positiveMin;
negativeMin = 0;
zeroPostion = 0;
positiveMin = 0;
int negativeCount = 0;
BOOL hasZero = false;
double result = 1;
for(i = 1; i < array.length; i ++){
    if(array[i] < 0){
        negativeCount ++;
        result *= array[i];
        if(array[i] > array[negativeMin]){
            negativeMin = i;
        }
    }else if(array[i] == 0){
        if(hasZero){
            return 0;// at least two zero elements in array. So result is zero
        }
        hasZero = true;
        zeroPosition = i;

    }else{
        result *= array[i];
        if(array[i] < array[positiveMin]){
            positiveMin = i;
        }
    }
}
//if code could execute to here, it means the array only contains one zero element at most. 
if(negativeCount%2 == 0){
   if(hasZero){
       return result;
   }else{
       return result /= array[positiveMin];
   }
}else{
       return result /= array[negativeMin];
}
}

`