โปรแกรมหากำไรสูงสุดจากการซื้อขายหุ้นพร้อมวันหยุดพักใน Python

สมมติว่าเรามีรายการราคาหุ้นเรียงตามเวลา หากำไรสูงสุดจากการซื้อขาย ต้องซื้อก่อนขาย และหลังขายต้องรอ 1 วัน (cooldown) จึงจะซื้อได้อีก

ตัวอย่าง

อินพุต: prices = [2, 6, 9, 4, 11]

เอาต์พุต: 11

ซื้าที่ 2 ขายที่ 6 (กำไร 4) รอ 1 วัน ซื้าที่ 4 ขายที่ 11 (กำไร 7) รวม 11

ขั้นตอนการแก้ปัญหา

ใช้ DP สองสถานะ: s = กำไรสูงสุดเมื่อไม่ถือหุ้น, b = กำไรสูงสุดเมื่อถือหุ้น (ค่าลบเพราะใช้เงินซื้อ)

1. s = 0, b = -inf
2. วนลูป i จาก 0 ถึง len(prices)-1:
   • temp = b
   • b = max(b, s - prices[i]) (ซื้อหรือถือต่อ)
   • ถ้า i > 0: s = max(s, temp + prices[i-1]) (ขายเมื่อวานหรือไม่ขาย)
3. คืนค่า max(s, b + prices[-1]) (ขายในวันสุดท้ายหรือไม่ขาย)

การนำไปใช้ใน Python

class Solution:
    def solve(self, prices):
        s = 0
        b = float("-inf")
        for i in range(len(prices)):
            temp = b
            b = max(b, s - prices[i])
            if i:
                s = max(s, temp + prices[i - 1])
        return max(s, b + prices[-1])

ob = Solution()
prices = [2, 6, 9, 4, 11]
print(ob.solve(prices))

อินพุต

[2, 6, 9, 4, 11]

เอาต์พุต

11