这是一个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;
}
}几点说明：
- 这是我做《如何设计完备可靠的测试用例》培训用的一个代码示范，在github上开源的：https://github.com/qinjx/lotusphp/blo…，会持续更新，敬请关注
- 我贴出来的测试用例只有“参数输入正确的正常流程”是100%做到了MECE（完全穷尽，彼此独立），“参数输入错误的异常流”还没做到MECE，极端情况的“白盒测试”就更谈不上MECE了，而且也没写测试方法体
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]
直接上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;
}
}不写代码了，直接上逻辑，既然是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)
实际上应该是个排序题吧，先取绝对值排序，再根据 0 和负数出现的情况直接算最大乘积。没必要把所有乘积都算一遍的。先记上记号，回头补作业。
首先一个事情是问题里 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 <sunyanzi@com.segmentfault>
* @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 …
就是这样 … 请测试 … 我有不及格的心理准备了恩恩 …
写个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不会写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];
}
}`
正文完