LeetCode-152. 乘积最大子数组-蒲公英云

LeetCode-152. 乘积最大子数组

思路

这题跟LeetCode-53. 最大子数组和很像
最后把整个 dp 数组看一遍求最大值即可。因此状态转移方程可能是：

dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

说明：牢记状态的定义，一定以下标 i 结尾，即：乘积数组中 nums[i] 必须被选取。

如果 dp[i - 1] 是负数，乘上 nums[i] 还是负数。
如果 nums[i] 是负数该怎么办呢？dp[i - 1] 是正数的时候，越乘越小，dp[i - 1] 是负数的时候，越乘越大，于是我们可能就需要记录一下负数的那个最小数。
遇到这样的问题，其实就在提示我们状态不够用了。因此，需要在原来的一维 dp 后面新增一个状态。
针对这道题，第 2 维状态只需要两个：

dp[i][1] 表示：以 nums[i] 结尾的连续子序列的乘积的最大值；
用 1 表示遍历的过程中得到的以 nums[i] 结尾的连续子序列的乘积的最大值。
dp[i][0] 表示：以 nums[i] 结尾的连续子序列的乘积的最小值。
用 0 表示遍历的过程中得到的以 nums[i] 结尾的连续子序列的乘积的最小值；

动态规划

1.确定dp数组以及下标的含义

dp[i][2]：包括下标i（以nums[i]为结尾）的乘积最大子数组积为dp[i]。

2.确定递推公式

我们要收集自己本身，之前的最大值×当前数,之前的最小值×当前数

dp[i][1] = Math.max(nums[i],Math.max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]));
dp[i][0] = Math.min(nums[i],Math.min(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]));

3.dp数组如何初始化

根据递推公式可知，可以推出我们要初始化dp[0][0]和dp[0][1]为当前数nums[0]
dp[0][0] = nums[0];
dp[0][1] = nums[0];

4.确定遍历顺序

根据递推公式可知，从左到右遍历

5.举例推导dp数组

在这里插入图片描述

代码实现

class Solution {
    public int maxProduct(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        int res = nums[0];
        for(int i = 1;i<nums.length;i++){
            dp[i][1] = Math.max(nums[i],Math.max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]));
            dp[i][0] = Math.min(nums[i],Math.min(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]));
            res = Math.max(res,dp[i][1]);
        }
        return res;
    }
}