152. 乘积最大子数组

**乘积最大子数组**

在算法中，乘积最大子数组是指一个数组的连续子序列，其元素的乘积最大。这个问题经常出现在竞赛或面试中。

**问题描述**

给定一个整数数组 `nums`，要求找到一个连续子数组，其元素的乘积最大，并返回该乘积。

**示例**

* 输入：`[-2,0, -1]`
输出：`0`
* 输入：`[0,1, -2,3,4, -5,6,7,8,9, -10]`
输出：`-10`

**解决方案**

我们可以使用动态规划来解决这个问题。动态规划是一种通过分解大问题为小子问题的方法，求出每个子问题的最优解，然后组合这些解以得出原问题的最优解。

### 动态规划首先，我们定义一个数组 `dp`，其中 `dp[i]` 表示从第0 个元素到第 i 个元素的乘积最大子数组的乘积。我们初始化 `dp[0] = nums[0]`。

接下来，我们遍历数组 `nums`，对于每个元素 `nums[i]`，我们计算 `dp[i] = max(dp[i-1]*nums[i], nums[i])`。这里，我们有两种情况：

* 如果 `dp[i-1]*nums[i] > nums[i]`，则 `dp[i] = dp[i-1]*nums[i]`。
* 否则，`dp[i] = nums[i]`。

###代码实现

class Solution:
 def maxProduct(self, nums: List[int]) -> int:
 if not nums:
 return0 # 初始化动态规划数组 dp = [0]*len(nums)
 # 初始化第一个元素 dp[0] = nums[0]
 # 遍历数组，计算乘积最大子数组的乘积 for i in range(1, len(nums)):
 if dp[i-1]*nums[i] > nums[i]:
 dp[i] = dp[i-1]*nums[i]
 else:
 dp[i] = nums[i]
 # 返回乘积最大子数组的乘积 return max(dp)

###代码注释* `if not nums: return0`：如果输入数组为空，则返回0。
* `dp = [0]*len(nums)`：初始化动态规划数组，长度为输入数组的长度。
* `dp[0] = nums[0]`：初始化第一个元素。
* `for i in range(1, len(nums)):`：遍历数组，从第二个元素开始计算乘积最大子数组的乘积。
* `if dp[i-1]*nums[i] > nums[i]: dp[i] = dp[i-1]*nums[i]`：如果前一个元素的乘积与当前元素相乘大于当前元素，则更新当前元素的乘积。
* `else: dp[i] = nums[i]`：否则，当前元素的乘积为其自身。
* `return max(dp)`：返回乘积最大子数组的乘积。

### 时间复杂度时间复杂度为 O(n)，其中 n 是输入数组的长度。因为我们只遍历一次数组。

### 空间复杂度空间复杂度为 O(n)，因为我们需要存储动态规划数组。