内容简介:动态规划题第三天
2 0 1 9 -5 -20 星 期一 开 始 吧
动态规划题第三天
题 目 描 述
给定一个整形数组,让我们求得乘积最大的连续子数组。这道题难点在于如果是遇到0最大值就会变成0,如果最大值碰到负数,就会变成负数最小值,两个负数相乘,又会变成正。
题目解析
还是这道题和之前的题目有点不一样,我们还是先按照之前说的先定义状态,然后求出状态转移方式。题目给的是一个一维数组,按照之前的逻辑我们定义一个状态。
状态转移方程
可能你已经知道了,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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode动态规划之PHP解析(120. Triangle)
- 解析 :跻身数据科学领域的五条职业规划道路
- Leetcode动态规划之PHP解析(70. Climbing Stairs)
- Leetcode动态规划之PHP解析(72. Edit Distance)
- Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)
- Leetcode动态规划之PHP解析(123. Best Time to Buy and Sell Stock III)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
细节决定交互设计的成败
张亮 / 2009-3 / 49.00元
《细节决定交互设计的成败》是一本非常实用的有关软件界面的交互设计和可用性设计方面知识的书籍,通过采用一问一答的形式,你将会有针对性地学习到一些能够很快应用在自己软件开发工作中的细节知识和诀窍。例如,如何减轻用户的等待感,如何预防和减少用户的使用错误等。另外,你会发现阅读《细节决定交互设计的成败》时会非常轻松和愉悦;这是由于《细节决定交互设计的成败》写作上的两个特点:第一,采用较多日常生活中的例子来......一起来看看 《细节决定交互设计的成败》 这本书的介绍吧!