Maximum Product Subarray ใน Python

หา subarray ที่ติดกัน (contiguous) ที่มีผลคูณมากที่สุด

ตัวอย่าง

Input: [2,3,-2,4,-5,-6,2]
Output: 240  # subarray [-2,4,-5,-6] หรือ [2,3,-2,4,-5,-6]? 
# จริงๆ: 3 * -2 * 4 * -5 * -6 * 2 = -1440 (ผิด)
# ถูกต้อง: 4 * -5 * -6 * 2 = 240

อัลกอริทึม Dynamic Programming (Kadane แบบ Product)

เก็บ max_ending_here และ min_ending_here เพราะ negative × negative = positive

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0
        max_prod = min_prod = result = nums[0]
        
        for n in nums[1:]:
            candidates = (n, max_prod * n, min_prod * n)
            max_prod = max(candidates)
            min_prod = min(candidates)
            result = max(result, max_prod)
        return result

# ทดสอบ
sol = Solution()
print(sol.maxProduct([2,3,-2,4,-5,-6,2]))  # 240
print(sol.maxProduct([-2,0,-1]))           # 0
print(sol.maxProduct([-2,3,-4]))           # 24

ความซับซ้อน

• Time: O(n)
• Space: O(1)

สรุป

ต้อง track ทั้ง max และ min เพราะค่าลบอาจกลายเป็น max เมื่อคูณกับลบอีกครั้ง