Leetcode # 152. Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/

Solution

參考 Leetcode # 53. Maximum Subarray (Kadane’s Algorithm)

※ 注意：
若先計算 max_ending_here 才計算 min_ending_here 會導致結果錯誤

〇

max_ending_here, min_ending_here = max(num, max_ending_here * num, min_ending_here * num), \
                                   min(num, max_ending_here * num, min_ending_here * num)

〇

temp_max = max(num, max_ending_here * num, min_ending_here * num)
min_ending_here = min(num, max_ending_here * num, min_ending_here * num)
max_ending_here = temp_max

×

max_ending_here = max(num, max_ending_here * num, min_ending_here * num)
min_ending_here = min(num, max_ending_here * num, min_ending_here * num)

完整程式碼：

class Solution:
  def maxProduct(self, nums: List[int]) -> int:
    max_so_far = max_ending_here = min_ending_here = nums[0]
    for num in nums[1:]:
      max_ending_here, min_ending_here = max(num, max_ending_here * num, \
                                                  min_ending_here * num), \
                                         min(num, max_ending_here * num, \
                                                  min_ending_here * num)
      max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Last Updated on 2023/08/16 by A1go