百度文库PHP面试题:给定一个整数数组,找出具有最大和的连续子数组,并返回最大和。

未分类 He Haoyuan 7个月前 (12-07) 549次浏览 0个评论

原始面试题目的要求如下:

给定一个整数数组,找出具有最大和的连续子数组,并返回最大和。
$nums = [-2,1 ,-3,4,-1,2,1,-5,4];
打印出最大和的连续子数组。

这道题看起来挺简单的。但是,我好久没写算法题了...写了10多分钟,没写完。我真的是变菜了😅。

上机实际写的时候,变量名起的太容易混淆了。例如:$num和$nums。我把变量名写错了好几次,导致查了半天的BUG。最后说了一下思路,面试官反馈思路正确。总之,面试估计是寄了。

题目的整体思路就是两个for循环,遍历整个数组。然后,计算当前循环数组值的相加之和。如果遇到最大的值,就记录下起始和结束的数组下标。最后打印即可。

下面是面试结束后重新写的代码,大约花费了20分钟左右,整体用时还是偏慢。看来面试还得多练算法题呀。

解题代码如下:

function index(){
    $nums = [-2,1 ,-3,4,-1,2,1,-5,4];

    $count = count($nums);
    $arr = [];
    $max_key = 0;
    $max_value = -999999;

    for ($i = 0; $i < $count; $i++){
        $min = $i;
        $max = 0;
        $old = 0;
        for ($j = $i; $j < $count; $j++){
            $new = $old + $nums[$j];
            if($new > $old){
                $max = $j;
                $old = $new;

                $arr[$i]['min'] = $min;
                $arr[$i]['max'] = $max;
                $arr[$i]['all'] = $new;

                if($new >= $max_value){
                    $max_key = $i;
                    $max_value = $new;
                }
            }
        }
    }

    $return = [];

    for ($i = 0; $i < $count; $i++){
        if ($i >= $max_key && $i <= $arr[$max_key]['max']){
            $return[] = $nums[$i];
        }
    }

    print_r($return);
}

何浩源的博客 , 何浩源版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:百度文库PHP面试题:给定一个整数数组,找出具有最大和的连续子数组,并返回最大和。
喜欢 (0)
发表我的评论
取消评论

已设置自动反垃圾评论保护检测,无需输入验证码。 *

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址