โปรแกรมหาผลคูณสูงสุดของซับอาร์เรย์ติดกันใน Python

สมมติว่าเรามีอาร์เรย์ nums เราต้องหาผลคูณของสมาชิกในซับอาร์เรย์ติดกัน (อย่างน้อย 1 ตัว) ที่มีผลคูณมากที่สุด

ตัวอย่าง: [1,9,2,0,2,5] ผลลัพธ์คือ 18 จากซับอาร์เรย์ [1,9,2]

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. สร้าง max_list และ min_list ขนาด len(nums) เติม 0
2. max_list[0] = min_list[0] = nums[0]
3. วนลูป i จาก 1 ถึง len(nums)-1:
   • max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
   • min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i])
4. คืนค่า max(max_list)

ตัวอย่างโค้ด Python

class Solution(object):
    def maxProduct(self, nums):
        max_list = [0] * len(nums)
        min_list = [0] * len(nums)
        max_list[0] = nums[0]
        min_list[0] = nums[0]
        for i in range(1, len(nums)):
            max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
            min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i])
        return max(max_list)

ob1 = Solution()
print(ob1.maxProduct([1,9,2,0,2,5]))  # Output: 18

อินพุต / เอาต์พุต

Input: [1,9,2,0,2,5]

Output: 18