# **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://www.youtube.com/watch?v=lXVy6YWFcRM
Provided by. NeetCode
###### tags: `arrays` `dynamic programming` `medium` `leetcode`
Sign in with Wallet
Connect another wallet