LeetCode-152. 乘积最大子数组

古城微笑少年丶 2024-03-24 17:27 93阅读 0赞

#### 目录 ####

*   *  思路
     *  动态规划

题目来源  
[152. 乘积最大子数组][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数组

![在这里插入图片描述][22da3746690d411e8944c6761dbaff56.png]

代码实现

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;
        }
    }

![在这里插入图片描述][54bb7aef73a04b94af3c823a0f501373.png]

[152.]: https://leetcode.cn/problems/maximum-product-subarray/
[22da3746690d411e8944c6761dbaff56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/99f6549b511d4868a6d12b28b43df065.png
[54bb7aef73a04b94af3c823a0f501373.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/78c0411958f94bd9b8bb623c46464530.png