用PHP解题

问题

给出一个数字数组,选择其中一个数字加1,再将所有的数字相乘
到底哪个数字加1会使得结果变成最大?

例1
numbers = {1, 2, 3}
Returns : 12

例2
numbers = {1, 3, 2, 1, 1, 3}
Returns : 36
数字可以不是唯一

例3
numbers = {1000, 999, 998, 997, 996, 995}
Returns : 986074810223904000

例4
numbers = {1, 1, 1, 1}
Returns : 2

自己家的解法

<?php
$numbers = array(1000, 999, 998, 997, 996, 995);
$target1 = 0;
for ($y = 0; $y < count($numbers); $y++) {
    $target2 = 1;
    $numbers[$y] = $numbers[$y] + 1;
    for ($i = 0; $i < count($numbers); $i++) {
        $target2 = $target2 * $numbers[$i];
    }
    $numbers[$y] = $numbers[$y] - 1;
    if ($target1 < $target2) {
        $target1 = $target2;
    }
}
echo $target1;



使用2层循环,如果数组的数字个数很大的时候,程序运行时会产生大量的循环。
而且代码没有方法化的原因,测试的时候交替修改数组内部的值这种方法并不推荐。

别人家的解法1

<?php
function check($arr)
{
    asort($arr);
    $arr = array_values($arr);
    $arr[0] += 1;
    return array_reduce($arr, function ($carry, $item) {
        $carry *= $item;
        return $carry;
    }, 1);
}

echo check(array(1000, 999, 998, 997, 996, 995));

和自己家的解法不同,不交替改写数组里的内容且将处理过程封装成一个方法。

别人家的解法2

<?php
function check($arr)
{
    sort($arr);
    $arr[0] += 1;
    return array_product($arr);
}

echo check(array(1000, 999, 998, 997, 996, 995));

总结

通过观察规律,数组排序后,第一个数字加1,就能保证所得结果是最大的,利用这一规则,就能在实践过程中,避免嵌套循环。
如何从自己家升级成别人家?善于发现规律,然后优雅去实践!

本文相关代码

https://github.com/cangyan/TAV/tree/master/00002_PHP_ARRAY_REDUCE

参考链接

http://qiita.com/y-i-p/items/7f426b652930ebc1f9c7 (orz原文的代码是有bug的)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注