Khóa học Python từ Cơ bản đến Nâng cao

Bài 10.4 - Bài toán tối ưu lợi nhuận trong Python

Một trong những bài toán cổ điển thường gặp trong lập trình là:
Cho danh sách giá cổ phiếu theo ngày, làm sao để mua và bán sao cho lợi nhuận là cao nhất.

Mô tả bài toán

Cho mảng prices, trong đó prices[i] là giá cổ phiếu ngày thứ i.
Bạn chỉ được mua 1 lần và bán 1 lần, sau ngày mua.

Yêu cầu: Tìm lợi nhuận tối đa có thể đạt được.

Ví dụ

prices = [7, 1, 5, 3, 6, 4]

• Mua ở giá 1, bán ở giá 6 → lợi nhuận = 6 - 1 = 5
  Output: 5

prices = [7, 6, 4, 3, 1]

• Giá giảm dần → không thể lãi
  Output: 0

Cách giải đơn giản và hiệu quả

Ý tưởng: Duyệt qua từng ngày, giữ giá thấp nhất tính đến hiện tại, và mỗi ngày tính lợi nhuận nếu bán hôm đó.

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)

    return max_profit

Ví dụ chạy:

print(max_profit([7, 1, 5, 3, 6, 4]))  # Output: 5
print(max_profit([7, 6, 4, 3, 1]))     # Output: 0

Cách này chạy rất nhanh với độ phức tạp O(n), chỉ cần 1 vòng lặp duy nhất.

Giải thích chi tiết

• min_price: là giá thấp nhất trước hoặc bằng ngày hiện tại.
• Với mỗi price, ta tính lợi nhuận nếu bán hôm nay → price - min_price.
• Cập nhật max_profit nếu lợi nhuận hiện tại tốt hơn.

Một số biến thể khác

1. Nếu được mua bán nhiều lần để tối đa hoá lợi nhuận?

def max_profit_multi(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

Ví dụ:

print(max_profit_multi([1, 2, 3, 4, 5]))  # Output: 4

Bạn được phép mua hôm trước, bán hôm sau nếu giá tăng. Có thể làm nhiều lần.

Phân tích độ phức tạp

Tổng kết

• Đây là bài toán rất tốt để luyện tư duy tối ưu tuyến tính và quản lý biến.
• Cách giải hiệu quả không dùng mảng phụ, chỉ cần duyệt 1 lần và cập nhật kết quả tối ưu.
• Cũng là bước đầu để học các bài toán nâng cao như “Best Time to Buy and Sell Stock II, III, IV”.