leetCode ✏Leetcode基础刷题之(152. Maximum Product Subarray)
✏描述
给定一个整形数组，让我们求得乘积最大的连续子数组。这道题难点在于如果是遇到0最大值就会变成0,如果最大值碰到负数，就会变成负数最小值，两个负数相乘，又会变成正。
✏题目实例
✏题目分析
还是这道题和之前的题目有点不一样，我们还是先按照之前说的先定义状态，然后求出状态转移方式。题目给的是一个一维数组，按照之前的逻辑我们定义一个状态。
DP[i]
代表从下标0到下标i这个范围内的连续子数组最大的乘积
状态转移方程
DP[i+1] = DP[i] * 当前下标的值
可能你已经知道了，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($res,$max[$i]);
}
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;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)