Best Time to Buy and Sell Stock

+10

Bạn nhận được một danh sách prices, trong đó prices[i] là giá của một cổ phiếu vào ngày i. Bạn có thể mua một cổ phiếu vào một ngày rồi bán vào một ngày sau đó. Hãy trả về lợi nhuận lớn nhất bạn có thể thu được, hoặc 0 nếu mọi giao dịch có thể thực hiện đều bị lỗ.

Hàm

maxProfit(prices: integer-array) → integer

pricesinteger-array: giá cổ phiếu mỗi ngày, theo thứ tự
Trả vềinteger: lợi nhuận lớn nhất từ một lần mua và một lần bán sau đó, hoặc 0

Ràng buộc

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Bạn thực hiện nhiều nhất một giao dịch, và bán vào một ngày sau ngày mua.

Ví dụ

Đầu vào: prices = [7, 2, 5, 9, 1, 4]
Đầu ra: 7
Giải thích: Mua vào ngày 1 với giá 2 và bán vào ngày 3 với giá 9, thu lợi nhuận 7. Giá thấp nhất là 1 vào ngày 4, sau mức giá 9, nên bán sau ngày đó chỉ thu được 3.

Câu hỏi mở rộng

Nếu bạn có thể giao dịch bao nhiêu lần tùy thích, nhưng mỗi lần chỉ nắm giữ tối đa một cổ phiếu thì sao?

Lời giải

Bạn phải mua trước khi bán, nên đáp án không phải là giá cao nhất trừ giá thấp nhất. Với mỗi ngày bạn có thể bán, ngày mua tốt nhất là ngày rẻ nhất trước đó. Theo dõi mức giá thấp nhất khi bạn lần lượt xét các ngày sẽ giúp giải bài toán chỉ trong một lượt duyệt.

Hãy thử mọi cặp mua và bán

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Mỗi giao dịch gồm một ngày mua và một ngày bán sau đó, vì vậy hãy thử mọi cặp và giữ lại mức chênh lệch lớn nhất. Bắt đầu với lợi nhuận tốt nhất là 0 để tính cả lựa chọn không giao dịch. Mọi giao dịch hợp lệ đều được kiểm tra, nên đáp án chính xác.

Danh sách gồm n mức giá có khoảng n²/2 cặp: 100,000 ngày tương đương khoảng 5 tỷ phép trừ.

Thuật toán

Đặt best thành 0.
Lặp qua từng ngày mua buy.
Với mỗi ngày, lặp qua từng ngày bán sell sau ngày đó.
Tính prices[sell] trừ prices[buy], rồi lưu vào best nếu kết quả lớn hơn.
Trả về best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

Một lượt duyệt với mức giá thấp nhất tính đến hiện tại

Ý tưởng

Xét ngày bán i. Ngày mua tốt nhất là ngày có giá thấp nhất tính đến i, vì vậy giao dịch tốt nhất kết thúc vào ngày i thu được prices[i] trừ đi mức giá thấp nhất tính đến thời điểm đó. Mỗi ngày bán được ghép với ngày mua tốt nhất, nên lợi nhuận lớn nhất trong các giao dịch đó là đáp án. Vào ngày có mức giá thấp nhất mới, lợi nhuận bằng 0, giống như không giao dịch.

Cách duyệt đọc mỗi mức giá một lần và lưu hai số, lowest và best: thời gian O(n) và bộ nhớ O(1).

Thuật toán

Đặt lowest bằng giá đầu tiên và best bằng 0.
Duyệt các mức giá theo thứ tự.
Nếu giá hiện tại thấp hơn lowest, hãy đặt nó thành lowest mới.
Tính giá hiện tại trừ lowest, rồi lưu kết quả vào best nếu kết quả lớn hơn.
Trả về best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Lỗi thường gặp và trường hợp biên

Trả về giá cao nhất trừ giá thấp nhất. Với [7, 2, 5, 9, 1, 4], kết quả là 8, nhưng giá 1 xuất hiện sau giá 9. Đáp án là 7.
Để đáp án trở thành số âm. Với [9, 7, 4, 3, 1], mức chênh lệch tốt nhất là -1; hãy đặt best bằng 0, không phải bằng mức chênh lệch đầu tiên.
Đặt lowest bằng 0. Khi đó, mọi khoản lợi nhuận đều bằng chính giá đó, nên [9, 7, 4, 3, 1] trả về 9. Hãy đặt giá trị này bằng giá đầu tiên.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Thời điểm tốt nhất để mua và bán cổ phiếu là bao nhiêu?

Giải pháp duyệt một lần có độ phức tạp thời gian O(n) với n ngày, vì giải pháp đọc mỗi mức giá một lần, và cần thêm O(1) bộ nhớ: mức giá thấp nhất tính đến thời điểm đó và lợi nhuận cao nhất. Thử mọi cặp ngày cần O(n²) thời gian.

Tại sao không lấy giá thấp nhất trừ giá cao nhất?

Giá thấp nhất có thể xuất hiện sau giá cao nhất, và bạn phải mua trước khi bán. Trong [7, 2, 5, 9, 1, 4], số 1 xuất hiện sau số 9, nên giao dịch tốt nhất được phép là mua ở giá 2 và bán ở giá 9 để lãi 7.

Best Time to Buy and Sell Stock có phải là một bài toán quy hoạch động không?

Bạn có thể nhìn nhận vấn đề theo cả hai cách. Mức giá thấp nhất tính đến thời điểm hiện tại là một phần trạng thái nhỏ mà bạn cập nhật mỗi ngày, đây là cách nhìn theo quy hoạch động. Ghép mỗi lần bán với ngày trước đó có giá thấp nhất là cách nhìn tham lam. Cả hai đều dẫn đến đoạn code chỉ cần duyệt một lượt.

def maxProfit(prices):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Đối số

prices = [7, 2, 5, 9, 1, 4]

Đầu ra mong đợi