---
# System prepended metadata

title: '**Leetcode筆記(Maximum Product Subarray)**'
tags: [arrays, medium, dynamic programming, leetcode]

---

# **Leetcode筆記(Maximum Product Subarray)**


:::info
:information_source: 題目 : Maximum Product Subarray, 類型 : arrays , 等級 : medium
日期 : 2023/02/18，2023/06/13，2023/11/19，2025/02/26
:::


### 嘗試

為了負負得正去設定第二個if條件，但沒已考慮到[-2]的資測

```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        submax = 1
        realmax = nums[0]
        nums.append(1)
        for i in range(len(nums)):
            submax = submax * nums[i]
            if submax >= 0:
                realmax = max(submax, realmax)
            else:
                if nums[i+1] < 0:
                    submax = submax
                submax = 1 # 推估這裡有問題
        return realmax
```
2023/06/13
設計兩個機制，一個控制當前這個數字前面所有的min，一個控制max，並且納入"自己"來比較，若是自己就很大or很小，那就放棄前面的累加，也納入"對方"來比較，例如min也納入max來考慮，為了也處理負數
ps.max min可以比三個
```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minRes, maxRes, tmp = 1, 1, 0 # tmp怕minRes跑值
        realMax = nums[0]

        for n in nums:
            tmp = minRes
            minRes = min(n, minRes * n, maxRes * n)
            maxRes = max(n, tmp * n, maxRes * n)
            realMax = max(realMax, maxRes)
        
        return realMax
```
2023/07/19
同上面的解釋，有兩個機制，防止
1. 某一個單獨極大or極小值的出現導致翻盤
2. 兩個負數出現導致負負得正翻盤
```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 用兩個變數去儲存目前為止的最大 最小 本身項
        tmpMax, tmpMin, resMax = 1, 1, nums[0]

        for n in nums:
            tmp = tmpMax
            tmpMax = max(n, tmpMax * n, tmpMin * n)
            tmpMin = min(n, tmp * n, tmpMin * n)
            resMax = max(resMax, tmpMax) # 只關注最大項
        
        return resMax
```
2023/11/19
```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        negMax, posMax, res = nums[0], nums[0], nums[0]
        if len(nums) == 1:
            return res

        for n in nums[1:]:
            oldNegMax = negMax
            negMax = min(n * negMax, n * posMax, n)
            posMax = max(n * oldNegMax, n * posMax, n)
            res = max(posMax, res)
        
        return res
```
2025/02/26
```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minN, maxN = nums[0], nums[0]
        golbalMax = nums[0]

        for n in nums[1:]:
            temp = minN
            minN = min(n, n * temp, n * maxN)
            maxN = max(n, n * temp, n * maxN)
            golbalMax = max(golbalMax, maxN)
        return golbalMax
```

---
### **優化**
設計一個max與min，以防止若有極小負數乘到下一個負數，變成正數，同時也加入n(自己本身)，去過濾掉n前方array過小的數值。
res直接使用nums最大值，可以處理[-2]或[5]等單獨array，直接輸出。
tmp是為了讓minAns中的maxAns不要受上一行的輸出影響。
```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = max(nums) # 為了處理只有一個數的array
        maxAns, minAns = 1, 1

        for n in nums:
            tmp = maxAns
            maxAns = max(n, n * maxAns, n * minAns)
            minAns = min(n, n * tmp, n * minAns)
            res = max(res, maxAns)
        return res
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success
res = max(nums)，直接使用nums的空間
三者比較並拋棄弱者n, n * maxAns, n * minAns
:::

**思路**
![](https://i.imgur.com/2Hy9RA5.png)

**講解連結**
https://www.youtube.com/watch?v=lXVy6YWFcRM
Provided by. NeetCode

###### tags:  `arrays` `dynamic programming` `medium` `leetcode`