What is the key pattern used to solve the Maximum Product Subarray problem?

The problem uses dynamic programming with state transitions, where you maintain both the maximum and minimum products to handle the effect of negative numbers.

How do negative numbers impact the Maximum Product Subarray problem?

Negative numbers flip the product sign. Thus, we track both the maximum and minimum products to ensure we can get the correct result when multiplying two negative numbers.

What is the time complexity of the solution for the Maximum Product Subarray problem?

The time complexity is O(n), as we only need to iterate through the array once, updating the max and min product values at each index.

Can the solution be optimized further?

The space complexity can be optimized to O(1) by only storing the current maximum and minimum products, which reduces unnecessary space usage.

How does the space optimization work in the Maximum Product Subarray solution?

Instead of storing the product for all subarrays, we only keep track of the maximum and minimum product up to each index, which reduces the space complexity to constant space O(1).

#152

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位整数。请注意，一个只包含一个元素的数组的乘积是这个元素的值。示例 1: 输入: nums = [2,3,-2,4] 输出: 6 …

数组动态规划

题目描述

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

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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都保证是一个 32-位 整数

lightbulb

解题思路

方法一：动态规划

我们定义两个变量 $f$ 和 $g$ ，其中 $f$ 表示以 $nums[i]$ 结尾的乘积最大子数组的乘积，而 $g$ 表示以 $nums[i]$ 结尾的乘积最小子数组的乘积。初始时 $f$ 和 $g$ 都等于 $nums[0]$ 。答案为所有 $f$ 中的最大值。

从 $i=1$ 开始，我们可以考虑将第 $i$ 个数 $nums[i]$ 添加到前面的乘积最大或者乘积最小的子数组乘积的后面，或者单独作为一个子数组乘积（即此时子数组长度只有 $1$ ）。我们将此前的乘积最大值记为 $ff$ ，乘积最小值记为 $gg$ ，那么 $f = \max(f, ff \times nums[i], gg \times nums[i])$ ，而 $g = \min(g, ff \times nums[i], gg \times nums[i])$ 。接下来，我们更新答案 $ans = \max(ans, f)$ ，然后继续计算下一个位置。

最后的答案即为 $ans$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。我们只需要遍历数组一次即可求得答案。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = f = g = nums[0]
        for x in nums[1:]:
            ff, gg = f, g
            f = max(x, ff * x, gg * x)
            g = min(x, ff * x, gg * x)
            ans = max(ans, f)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain how negative numbers affect the product and how this is handled in the solution?
question_mark
Does the candidate demonstrate an understanding of dynamic programming techniques, specifically state transition?
question_mark
How efficiently can the candidate discuss and apply space optimization in dynamic programming problems?

warning

常见陷阱

外企场景

error
Forgetting to handle negative numbers correctly and assuming that the largest product will always be from the largest values.
error
Not considering zero as a product, which could reset the subarray product.
error
Using excessive space by storing all subarray products instead of just tracking the current max and min products.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to consider circular subarrays where the subarray can wrap around the array.
arrow_right_alt
Extend the problem to handle larger integer ranges, potentially using BigInteger or similar data types.
arrow_right_alt
Introduce a constraint where the array has multiple zeroes, and check if the algorithm handles this efficiently.

help

常见问题

外企场景

继续练习

#140 单词拆分 II #139 单词拆分 #174 地下城游戏