Leetcode动态规划之PHP解析(152. Maximum Product Subarray)

栏目: PHP · 发布时间: 5年前

内容简介:动态规划题第三天

2 0 1 9 -5 -20   期一    

动态规划题第三天

Leetcode动态规划之 <a href='https://www.codercto.com/topics/18749.html'>PHP</a> 解析(152. Maximum Product Subarray)

给定一个整形数组,让我们求得乘积最大的连续子数组。这道题难点在于如果是遇到0最大值就会变成0,如果最大值碰到负数,就会变成负数最小值,两个负数相乘,又会变成正。

题目解析

还是这道题和之前的题目有点不一样,我们还是先按照之前说的先定义状态,然后求出状态转移方式。题目给的是一个一维数组,按照之前的逻辑我们定义一个状态。

Leetcode动态规划之PHP解析(152. Maximum Product Subarray)

状态转移方程

Leetcode动态规划之PHP解析(152. Maximum Product Subarray)

可能你已经知道了,DP保存的是当前位置连续子数组的最大的乘积,但是我们并不知道当前下标的值是负数还是正数,如果是负数,那么DP[i+1]将会是一个最小值,所以只是单纯的这样定义状态是不行的。如果是负数的话,我们就应该选取前面推出的负数最大值也就是整个最小值。如果是正数的话我们才应该把之前的最大DP拿过来直接相乘,所以这里需要定义两个状态。

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxProduct($nums) {
        $max[0]=$min[0]=$res=$nums[0];
        for($i=1;$i<count($nums);$i++){
            $max[$i]=max($max[$i-1]*$nums[$i],$min[$i-1]*$nums[$i],$nums[$i]);
            $min[$i]=min($max[$i-1]*$nums[$i],$min[$i-1]*$nums[$i],$nums[$i]);
            $res=max($max[$i],$res);
        }
        
        return $res;
    }

如果这样看着不爽可以换一种.

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxProduct($nums) {
         $max=$min=$res=$nums[0];
        for($i=1;$i<count($nums);$i++){
            $mx=$max;
            $mn=$min;
            $max=max(max($nums[$i],$nums[$i]*$mx),$nums[$i]*$mn);
            $min=min(min($nums[$i],$nums[$i]*$mx),$nums[$i]*$mn);
            $res=max($res,$max);
        }
        return $res;
    }

Github整理地址: https://github.com/wuqinqiang/leetcode-php


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

动画的时间掌握

动画的时间掌握

哈罗德•威特克、约翰•哈拉斯 / 中国电影出版社 / 2012-7-1 / 38.00元

动画的时间掌握(修订版),ISBN:9787106035334,作者:(英)哈罗德·威特克 等著一起来看看 《动画的时间掌握》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试