Maximum Product Subarray
2022 年 5 月 24 日
![](https://i0.wp.com/lazyinwork.com/wp-content/uploads/2022/05/image-29.png?resize=678%2C673&ssl=1)
題目會給我們一段數列,要我們找出其中一段連續數乘機最大。
DP
主要概念就我們可以透過前一個點的『最大』與『最小』,來找出後一個點可能的『最大』與『最小』。
當然,後一個點的點值,也有可能是『最大』或『最小』,所有不要忘了多加上後一個點的點值。
def maxProduct(self, nums: List[int]) -> int:
numsLength = len(nums)
dp = [[]]*numsLength
dp[0] = [nums[0],nums[0]]
maxValue = nums[0]
for end in range(1,numsLength):
previousNode = dp[end-1]
nowNodeVal = nums[end]
temp = [
previousNode[0]*nowNodeVal,
previousNode[1]*nowNodeVal,
nowNodeVal
]
maxV, minV = max(temp), min(temp)
dp[end] = [maxV,minV]
if maxV > maxValue:
maxValue = maxV
return maxValue