0152. 乘積最大子數組 · ttttt

# 0152. 乘積最大子數組 ## 題目地址(152. 乘積最大子數組) <https://leetcode-cn.com/problems/maximum-product-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。示例 1: 輸入: [2,3,-2,4] 輸出: 6 解釋: 子數組 [2,3] 有最大乘積 6。示例 2: 輸入: [-2,0,-1] 輸出: 0 解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。 ``` ``` ## 前置知識 - 滑動窗口 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路這道題目要我們求解連續的 n 個數中乘積最大的積是多少。這里提到了連續，筆者首先想到的就是滑動窗口，但是這里比較特殊，我們不能僅僅維護一個最大值，因此最小值（比如-20）乘以一個比較小的數（比如-10）可能就會很大。因此這種思路并不方便。首先來暴力求解,我們使用兩層循環來枚舉所有可能項，這種解法的時間復雜度是O(n^2), 代碼如下： ``` <pre class="calibre18">``` var maxProduct = function(nums) { let max = nums[0]; let temp = null; for (let i = 0; i < nums.length; i++) { temp = nums[i]; for (let j = i + 1; j < nums.length; j++) { temp *= nums[j]; max = Math.max(temp, max); } } return max; }; ``` ``` 前面說了`最小值（比如-20）乘以一個比較小的數（比如-10）可能就會很大` 。因此我們需要同時記錄乘積最大值和乘積最小值，然后比較元素和這兩個的乘積，去不斷更新最大值。當然，我們也可以選擇只取當前元素。因此實際上我們的選擇有三種，而如何選擇就取決于哪個選擇帶來的價值最大（乘積最大或者最小）。 ![](https://img.kancloud.cn/bc/2c/bc2cf653ac28565f7172c66e943e8f20_603x308.jpg) 這種思路的解法由于只需要遍歷一次，其時間復雜度是O(n)，代碼見下方代碼區。 ## 關鍵點 - 同時記錄乘積最大值和乘積最小值## 代碼代碼支持：Python3，JavaScript Python3 Code: ``` <pre class="calibre18">``` class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) max__dp = [1] * (n + 1) min_dp = [1] * (n + 1) ans = float('-inf') for i in range(1, n + 1): max__dp[i] = max(max__dp[i - 1] * nums[i - 1], min_dp[i - 1] * nums[i - 1], nums[i - 1]) min_dp[i] = min(max__dp[i - 1] * nums[i - 1], min_dp[i - 1] * nums[i - 1], nums[i - 1]) ans = max(ans, max__dp[i]) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 當我們知道動態轉移方程的時候，其實應該發現了。我們的dp\[i\] 只和 dp\[i - 1\]有關，這是一個空間優化的信號，告訴我們`可以借助兩個額外變量記錄即可`。 Python3 Code: ``` <pre class="calibre18">``` class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) a = b = 1 ans = float('-inf') for i in range(1, n + 1): temp = a a = max(a * nums[i - 1], b * nums[i - 1], nums[i - 1]) b = min(temp * nums[i - 1], b * nums[i - 1], nums[i - 1]) ans = max(ans, a) return ans ``` ``` JavaScript Code: ``` <pre class="calibre18">``` var maxProduct = function(nums) { let max = nums[0]; let min = nums[0]; let res = nums[0]; for (let i = 1; i < nums.length; i++) { let tmp = min; min = Math.min(nums[i], Math.min(max * nums[i], min * nums[i])); // 取最小 max = Math.max(nums[i], Math.max(max * nums[i], tmp * nums[i])); /// 取最大 res = Math.max(res, max); } return res; }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經30K star啦。大家也可以關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解