Bài toán

Bạn được cung cấp một mảng số nguyên prices, trong đó prices[i] là giá của một cổ phiếu vào ngày thứ i.

Mỗi ngày, bạn có thể quyết định mua và/hoặc bán cổ phiếu. Tuy nhiên, bạn chỉ được giữ tối đa một cổ phiếu tại một thời điểm. Bạn cũng có thể mua và bán ngay trong cùng một ngày.

Hãy tìm và trả về lợi nhuận tối đa mà bạn có thể đạt được.

Ví dụ minh họa

Đầu vào: prices = [7, 1, 5, 3, 6, 4] Đầu ra: 7 Giải thích: Mua vào ngày 2 (giá = 1) và bán vào ngày 3 (giá = 5), lợi nhuận = 5 - 1 = 4. Mua vào ngày 4 (giá = 3) và bán vào ngày 5 (giá = 6), lợi nhuận = 6 - 3 = 3. Tổng lợi nhuận = 4 + 3 = 7.

Cách 1: Greedy algorithm

Độ phức tạp: Thời gian: 𝑂(𝑛) Không gian: O(1)

Ý tưởng: Nếu giá ngày sau cao hơn giá ngày trước, ta mua ở ngày trước và bán ở ngày sau để lấy lợi nhuận. Tích lũy lợi nhuận cho từng khoảng tăng giá.

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:  # Nếu giá tăng, ta thu lợi nhuận
            profit += prices[i] - prices[i - 1]
    return profit

Cách 2: Dynamic Programming

Ý tưởng: Dùng hai trạng thái: hold: Lợi nhuận tối đa khi đang giữ cổ phiếu. not_hold: Lợi nhuận tối đa khi không giữ cổ phiếu. Cập nhật hai trạng thái này theo từng ngày.

def maxProfit(prices):
    hold, not_hold = -float('inf'), 0  # Bắt đầu với trạng thái không có lợi nhuận
    for price in prices:
        hold = max(hold, not_hold - price) # Giữ hoặc mua mới
        not_hold = max(not_hold, hold + price)  # Giữ trạng thái hoặc bán
    return not_hold

References

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/