Giới thiệu

Bài toán của chúng ta là tìm ra lợi nhuận tối đa có thể đạt được từ việc mua và bán cổ phiếu qua một dãy giá liên tiếp. Trong bài viết này, chúng ta sẽ khám phá hai phương pháp khác nhau để giải quyết vấn đề này: thuật toán tham lam (greedy) và lập trình động (dynamic programming).

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ó quyền quyết định mua hoặc bán cổ phiếu. Tuy nhiên, bạn phải nhớ rằng chỉ được giữ tối đa một cổ phiếu tại một thời điểm, và bạn cũng có thể thực hiện việc mua và bán ngay trong cùng một ngày. Mục tiêu của bạn là tìm và trả về lợi nhuận tối đa mà bạn có thể đạt được từ những giao dịch này.

Ví dụ minh họa

Xét ví dụ sau:

Đầu vào: prices = [7, 1, 5, 3, 6, 4]
Đầu ra: 7
Giải thích:

• Mua vào ngày thứ 2 (giá = 1) và bán vào ngày thứ 3 (giá = 5), lợi nhuận = 4.
• Mua vào ngày thứ 4 (giá = 3) và bán vào ngày thứ 5 (giá = 6), lợi nhuận = 3.
• Tổng lợi nhuận = 4 + 3 = 7.

Cách 1: Thuật toán tham lam

Độ phức tạp:

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

Ý tưởng: Nếu giá ngày hôm sau cao hơn giá ngày hôm trước, chúng ta nên mua cổ phiếu vào ngày trước và bán vào ngày sau để thu lợi nhuận. Tích lũy lợi nhuận cho từng khoảng thời gian khi giá tăng.

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: Lập trình động

Ý tưởng:
Chúng ta sẽ sử dụng hai trạng thái để tính toán lợi nhuận tối đa: hold là lợi nhuận tối đa khi đang giữ cổ phiếu, và not_hold là lợi nhuận tối đa khi không giữ cổ phiếu. Các trạng thái này sẽ được cập nhật 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

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu cách để tối ưu hóa lợi nhuận mua bán cổ phiếu thông qua hai cách tiếp cận khác nhau: thuật toán tham lam và lập trình động. Mỗi phương pháp đều có những ưu điểm riêng, phù hợp với các tình huống khác nhau trong việc giao dịch cổ phiếu.

Tài liệu tham khảo

Bạn có thể tìm hiểu thêm tại: LeetCode - Best Time to Buy and Sell Stock II
source: viblo