乘积最大的子数组

Leetcode Link: 152. 乘积最大子数组 - 力扣（LeetCode）

题目

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

解法一

思路： 动态规划

没想出来怎么作为递归来做，同时也不适用于从左到右的尝试模型

本题最特殊的地方在于可能最小值遇到负数后变为最大值，因此再维护最大值的时候需要同时维护最小值，因此dp时需要两个一维dp表dp_max[]和dp_min[]

按照动规五步走（以dp_max为例）：

1. dp_max[i]表示以第 i 位结尾（含）的子数组的最大乘积
2. 递归公式：dp_max[i] = max(dp_min[i]*nums[i], dp_min[i]*nums[i], nums[i])
3. 初始化：dp_max[0]= nums[0]
4. 遍历方向：正常遍历
5. 尝试

本题中的坑

1. dp_max[i]表示的是以当前结尾的子数组中的最大乘积，并不一定是全局的最大乘积，也就是说，子问题和原问题实际上是有区别的。
2. 同时需要注意维护一个最小值的 dp 表
3. 区分本题和从左到右的模型的区别，本题的暴力递归我暂时不会，同时本题的特点是连续的，从左到右的模型可能不适合连续的情况。

题解：

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp_max = [None] * len(nums)
        dp_min = [None] * len(nums)
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
            dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
            res = max(dp_max[i], res)
        return res

最重要

本题关键在于存在负数，导致遇到负数后最小值可能变成最大值，同时最大值变成最小值，因此不仅需要维护一个最大值，也要维护一个最小值。 同时dp_max[i]并不是前i位置中的最大子串乘积，而是以i结尾的最大

启发和联系