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

Cho danh sách prices giá cổ phiếu theo thời gian. Tìm lợi nhuận tối đa từ tối đa 2 lần mua/bán (phải mua trước bán).

Ví dụ: prices=[2,6,3,4,2,9] → output 11 (mua 2 bán 6, mua 2 bán 9).

Thuật toán Greedy 4 biến trạng thái (O(n) time, O(1) space):

• first_buy = max profit sau lần mua 1 (âm: -price)
• first_sell = max profit sau lần bán 1
• second_buy = max profit sau lần mua 2 (dùng profit từ first_sell)
• second_sell = max profit sau lần bán 2 (đáp án)

Cập nhật lần lượt cho mỗi price:

first_buy = max(first_buy, -price)
first_sell = max(first_sell, first_buy + price)
second_buy = max(second_buy, first_sell - price)
second_sell = max(second_sell, second_buy + price)

Triển khai

class Solution:
    def solve(self, prices):
        first_buy = first_sell = float("-inf")
        second_buy = second_sell = float("-inf")
        
        for px in prices:
            first_buy = max(first_buy, -px)
            first_sell = max(first_sell, first_buy + px)
            second_buy = max(second_buy, first_sell - px)
            second_sell = max(second_sell, second_buy + px)
        
        return max(0, first_sell, second_sell)

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

Đầu vào

[2, 6, 3, 4, 2, 9]

Đầu ra

11

Giải thích: Mô hình hóa 4 trạng thái: chưa mua, đã mua 1, đã bán 1, đã mua 2, đã bán 2. Mỗi bước cập nhật giá trị tốt nhất có thể đạt được. Khởi tạo -inf vì chưa có giao dịch nào. Kết quả = max(0, first_sell, second_sell) vì có thể không giao dịch.

Mở rộng: Cho k giao dịch: DP O(k×n) với mảng buy[k+1], sell[k+1]. Khởi tạo buy[i] = -inf, sell[i] = 0. Cập nhật tương tự.