โปรแกรมหากำไรสูงสุดจากการซื้อขายหุ้นพร้อมค่าธรรมเนียมใน Python

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

ตัวอย่าง

อินพุต: prices = [2, 10, 4, 8], fee = 3

เอาต์พุต: 6

ซื้าที่ 2 ขายที่ 10 กำไร 8 - fee 3 = 5, ซื้าที่ 4 ขายที่ 8 กำไร 4 - fee 3 = 1 รวม 6

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

ใช้ DP แบบเวียนเกิด (recursion) สองสถานะ: ถือหุ้น (flag=1) หรือไม่ถือ (flag=0)

1. n = len(prices)
2. ฟังก์ชัน recur(i, flag):
   • ถ้า i == n คืน 0
   • ถ้า flag == 0 (ไม่ถือ): คืน max ของ recur(i+1, 1) - prices[i] (ซื้อ) และ recur(i+1, 0) (ไม่ซื้อ)
   • ถ้า flag == 1 (ถือ): คืน max ของ recur(i+1, 1) (ถือต่อ) และ recur(i+1, 0) + prices[i] - fee (ขาย)
3. เรียก recur(0, 0)

หมายเหตุ: วิธีนี้เป็น exponential time ควรใช้ memoization หรือ iterative DP เพื่อประสิทธิภาพ

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

class Solution:
    def solve(self, prices, fee):
        n = len(prices)
        def recur(i=0, flag=0):
            if i == n:
                return 0
            if not flag:
                return max(recur(i + 1, 1) - prices[i], recur(i + 1, 0))
            return max(recur(i + 1, 1), recur(i + 1, 0) + prices[i] - fee)
        return recur()

ob = Solution()
prices = [2, 10, 4, 8]
fee = 3
print(ob.solve(prices, fee))

อินพุต

[2, 10, 4, 8], 3

เอาต์พุต

6