乘积最大子数组

柔情只为你懂 2022-12-08 01:47 366阅读 0赞

# 乘积最大子数组 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/maximum-product-subarray/

## 2、题目要求 ##

题目描述

给你一个整数数组 `nums` ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

**示例 1:**

输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。

**示例 2:**

输入: [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

## 3、代码思路 ##

动态规划

1.  还是老样子，问自己一句：为什么需要使用动态规划呢？假设我们求出了每个以 `nums[i]` 结尾的最大连续子数组的乘积，那么从其中选出最大的乘积，不就是整个数组的最大连续子数组的乘积吗？
2.  但是这道题远没有这么简单，我们还需要根据 `nums[i]` 的正负来编写状态转移方程：如果 `nums[i]` 为负数，那么我们希望以 `nums[i-1]` 结尾的连续子数组的乘积越小越好，这样以 `nums[i]` 结尾的连续子数组的乘积则越大；如果 `nums[i]` 为正数，那么我们希望以 `nums[i-1]` 结尾的连续子数组的乘积越大越好，这样以 `nums[i]` 结尾的连续子数组的乘积则越大

--------------------

经过上面的分析，我们发现需要两个 `dp[]` 数组，

1.  一个 `dpMin[]` 数组：用于记录以 `nums[i]` 结尾的最小连续子数组的乘积，状态转移方程为：`dpMin[i] = Math.min(nums[i] * dpMin[i - 1], Math.min(nums[i], dpMax[i - 1] * nums[i]));`，其含义为选出以 `nums[i]` 结尾的最小连续子数组的乘积，从如下三种方案中选出最小值：`nums[i]` 自成一派；`nums[i]` 乘以以 `nums[i-1]` 结尾的最小连续子数组的乘积；`nums[i]` 乘以以 `nums[i-1]` 结尾的最大连续子数组的乘积
2.  一个 `dpMax[]` 数组：用于记录以 `nums[i]` 结尾的最大连续子数组的乘积，状态转移方程为：`dpMax[i] = Math.max(nums[i] * dpMin[i - 1], Math.max(nums[i], dpMax[i - 1] * nums[i]));`，其含义为选出以 `nums[i]` 结尾的最大连续子数组的乘积，从如下三种方案中选出最大值：`nums[i]` 自成一派；`nums[i]` 乘以以 `nums[i-1]` 结尾的最小连续子数组的乘积；`nums[i]` 乘以以 `nums[i-1]` 结尾的最大连续子数组的乘积

## 4、代码实现 ##

代码

class Solution {
        
        public int maxProduct(int[] nums) {
        
            // 用于记录以 nums[i] 结尾的最小连续子数组的乘积
            int[] dpMin = new int[nums.length];
            // 用于记录以 nums[i] 结尾的最大连续子数组的乘积
            int[] dpMax = new int[nums.length];
            // 当数组只有一个元素时，默认最大乘积为 nums[0]
            int maxProduct = nums[0];
            // 当数组只有一个元素时，默认 dpMin[0] 为 nums[0]
            dpMin[0] = nums[0];
            // 当数组只有一个元素时，默认 dpMax[0] 为 nums[0]
            dpMax[0] = nums[0];
    
            // 遍历数组，以每个 nums[i] 结尾
            for (int i = 1; i < nums.length; i++) {
        
                // 求出以 nums[i] 结尾的最大连续子数组的乘积
                dpMin[i] = Math.min(nums[i] * dpMin[i - 1], Math.min(nums[i], dpMax[i - 1] * nums[i]));
                // 求出以 nums[i] 结尾的最大连续子数组的乘积
                dpMax[i] = Math.max(nums[i] * dpMin[i - 1], Math.max(nums[i], dpMax[i - 1] * nums[i]));
                // 更新最大连续子数组的乘积
                maxProduct = Math.max(maxProduct, dpMax[i]);
            }
    
            return maxProduct;
        }
    }