佚名通过本文主要向大家介绍了[摆个擂台]设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：[摆个擂台]设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积
描述:
描述:
这是一个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_z