Chương trình tìm lợi nhuận tối đa mua bán cổ phiếu có cooldown trong Python

Cho danh sách giá cổ phiếu prices. Tìm lợi nhuận tối đa từ việc mua/bán nhiều lần với điều kiện: sau khi bán phải chờ 1 ngày (cooldown) mới được mua lại.

Ví dụ

prices = [2, 6, 9, 4, 11]

Mua 2, bán 6 (lãi 4), cooldown ngày 3, mua 4, bán 11 (lãi 7) → tổng 11.

Thuật toán (DP 2 trạng thái tối ưu)

Giữ 2 biến:

• s (sold/not holding): lợi nhuận tối đa khi không nắm cổ phiếu ngày hôm nay.
• b (bought/holding): lợi nhuận tối đa khi đang nắm cổ phiếu ngày hôm nay.

Cập nhật:

• new_b = max(b, s - price) (giữ hoặc mua hôm nay)
• new_s = max(s, old_b + prev_price) (giữ hoặc bán hôm qua - do cooldown)

Triển khai Python

class Solution:
    def solve(self, prices):
        if not prices:
            return 0
        s = 0              # không nắm stock
        b = float('-inf')  # nắm stock
        for i, price in enumerate(prices):
            prev_b = b
            b = max(b, s - price)
            if i > 0:
                s = max(s, prev_b + prices[i-1])
        return max(s, b + prices[-1])

# Test
ob = Solution()
print(ob.solve([2, 6, 9, 4, 11]))  # Output: 11

Giải thích trạng thái

• s: đã bán xong, đang trong trạng thái cooldown hoặc rảnh.
• b: đã mua, đang nắm stock.
• Khi bán ngày i, tiền nhận được là b + prices[i], nhưng do cooldown, trạng thái s chỉ cập nhật từ bán ngày i-1.

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).

Bài toán "Best Time to Buy and Sell Stock with Cooldown" (LeetCode 309).