題目出處

152. Maximum Product Subarray

難度

medium

個人範例程式碼

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        max_product = [0 for _ in range(len(nums))]
        min_product = [0 for _ in range(len(nums))]

        for i, num in enumerate(nums):
            if i > 0:
                if num > 0:
                    max_product[i] = max(num, num * max_product[i-1]) # only me, or bigger (smaller)
                    min_product[i] = min(num, num * min_product[i-1])
                else:
                    max_product[i] = max(num, num * min_product[i-1])
                    min_product[i] = min(num, num * max_product[i-1])
            else:
                max_product[0] = nums[0]                 
                min_product[0] = nums[0]

        # print(max_product)
        # print(min_product)

        return max(max_product)

算法說明

看起來複雜的問題，想一下發現最主要在搞事的就是負號，
因為正常來說，我們一直乘整數，數字只會一直不斷變大，
因此這樣的話，「我們唯一要思考的就只有負號的處理」

為了處理負號，我們同時記錄「至當前數字的 min 與 max 的 dp」，
紀錄時，我們要比較的內容也是關鍵，

我們要比較：「當前數字，與之前的內容乘上該數字是誰大(小)」，
而保留當前數字的原因，因為保留當前數字也等於，
「表示前面我們不要了，只保留當前數字下來繼續往後乘」

因此：

• 當 nums[i] >= 0 :
  • max_dp[i] = max(nums[i], nums[i]*max[i-1])
  • min_dp[i] = min(nums[i], nums[i]*min[i-1])
• 當 nums[i] < 0 :
  • max_dp[i] = max(nums[i], nums[i]*min[i-1])
  • min_dp[i] = min(nums[i], nums[i]*max[i-1])

而初始化：

max_dp[0] = min_dp[0] = nums[0]

或者，我們也可以這樣簡化

根據我們上面的討論，其實我們都知道我們要比較的就只有

「當前數字 (表示前面我們不要了，只保留當前數字下來繼續往後乘)」、
「nums[i]min[i-1]」、
「nums[i]max[i-1]」

同時取 max, min 記錄下來即可。

• 因此簡化後的結果就是：

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        max_product = [0 for _ in range(len(nums))]
        min_product = [0 for _ in range(len(nums))]

        for i, num in enumerate(nums):
            if i > 0:
                max_product[i] = max(num, num * max_product[i-1], num * min_product[i-1])
                min_product[i] = min(num, num * max_product[i-1], num * min_product[i-1])
            else:
                max_product[0] = nums[0]                 
                min_product[0] = nums[0]

        return max(max_product)

input handling

一同在 dp 內處理

Boundary conditions

用 for 迴圈控制範圍

Reference

• 乘积最大子序列 · Maximum Product Subarray