Best Time to Buy and Sell Stock: theo dõi minimum đang chạy

prices = [7,1,5,3,6,4] — đáp án là 5. Mua ở index 1, bán ở index 4. Khoảng chênh lệch từ 1 lên 6 là spread sinh lợi rộng nhất trong mảng. Vấn đề là tìm nó mà không kiểm tra từng cặp.

Những gì constraints buộc bạn phải làm

Mảng có thể dài đến 10⁵ phần tử. Ràng buộc đó thôi đã giết chết brute force trước khi bạn viết một dòng — 10⁵ bình phương là 10¹⁰ operations, không judge nào chịu đợi. Giá nằm trong khoảng 0 đến 10⁴, vừa gọn trong int, không lo overflow. Độ dài mảng tối thiểu là 1, có nghĩa là không giao dịch vẫn là kết quả hợp lệ: nếu chỉ có một giá, không thể bán, hàm trả về 0.

Hai điều đó cộng lại — "phải tuyến tính" và "trả về 0 nếu không có profit" — xác định hình dạng của giải pháp trước khi bạn bắt đầu thiết kế thuật toán.

Brute force: thử mọi cặp

Đọc bài theo nghĩa đen nhất: với mỗi ngày mua i, kiểm tra mọi ngày bán j > i và giữ profit tốt nhất.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        max_profit = 0
        n = len(prices)
        for i in range(n - 1):
            for j in range(i + 1, n):
                max_profit = max(max_profit, prices[j] - prices[i])
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int maxProfit = 0;
        int n = prices.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                maxProfit = Math.Max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}

O(n²) time, O(1) space. Đúng với mọi input. Vẫn timeout với n = 10⁵.

Duyệt qua [7,1,5,3,6,4] để thấy hình dạng. Khi i = 0 (mua ở giá 7), mọi ngày bán đều cho profit âm trừ giá 5, nhưng 5 - 7 = -2 vẫn âm. Khi i = 1 (mua ở giá 1), vòng lặp trong tính 5-1=4, 3-1=2, 6-1=5, 4-1=3. Max là 5. Không ngày mua nào sau đó vượt qua được. Đáp án: 5.

Sự thừa thãi rõ ràng: với mỗi ngày bán j, vòng lặp trong tìm ngược lại qua mọi ngày trước để tìm giá mua rẻ nhất. Nhưng một khi đã quét ngày 0 đến j-1, bạn đã biết minimum trong khoảng đó rồi. Chỉ cần mang nó về phía trước.

Giải pháp O(n): sliding window / running minimum

Insight gói trong một câu: để tối đa hóa profit khi bán vào ngày j, hãy mua vào ngày rẻ nhất trước j. Không cần tìm ngày rẻ nhất đó mỗi lần — duy trì nó như một running minimum trong khi quét từ trái sang phải.

Framing sliding window làm điều này rõ ràng. Con trỏ trái L là ngày mua; con trỏ phải R là ngày bán. Cả hai bắt đầu ở index 0 và R quét từ index 1. Ở mỗi bước:

• Nếu prices[R] < prices[L], con trỏ phải tìm thấy điểm entry rẻ hơn. Di chuyển L đến R — ngày mua cũ không còn liên quan.
• Ngược lại, prices[R] - prices[L] là profit ứng cử viên. Cập nhật maximum đang chạy.
• Luôn tăng R.

Không con trỏ nào bao giờ lùi lại. Mỗi phần tử được truy cập đúng một lần. Đó là lý do thuật toán là O(n).

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        left, right = 0, 1
        max_profit = 0
 
        while right < len(prices):
            if prices[right] < prices[left]:
                left = right
            else:
                max_profit = max(max_profit, prices[right] - prices[left])
            right += 1
 
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int left = 0, right = 1;
        int maxProfit = 0;
 
        while (right < prices.Length) {
            if (prices[right] < prices[left]) {
                left = right;
            } else {
                maxProfit = Math.Max(maxProfit, prices[right] - prices[left]);
            }
            right++;
        }
 
        return maxProfit;
    }
}

Duyệt tay qua [7,1,5,3,6,4]:

L dừng ở index 1 ngay lập tức và không bao giờ di chuyển nữa — giá 1 là minimum toàn cục và mọi ngày sau đó đều đắt hơn. Spread tối đa được ghi nhận ở bước 4.

Tiếp tục với ví dụ 2, [7,6,4,3,1]:

Giá giảm mỗi ngày. L đuổi theo R khắp mảng; nhánh else không bao giờ được chạy. max_profit ở mức 0 — không có giao dịch nào sinh lợi, nên không giao dịch.

Dạng running minimum

Bạn cũng sẽ thấy cách viết này mà không có tên pointer tường minh:

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        max_profit = 0
        for price in prices[1:]:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)
        return max_profit

public class Solution {
    public int MaxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.Length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = Math.Max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }
}

Về mặt cơ học giống hệt nhau. min_price là vị trí của con trỏ trái; vòng for là con trỏ phải tiến lên. Framing thay đổi, computation thì không. Tôi thích dạng pointer tường minh khi giải thích vì nó làm cấu trúc window hiện rõ — nhưng dạng running minimum gọn hơn và đúng như nhau. Trong interview thực tế, tôi sẽ viết dạng running minimum vì nó bám sát ngôn ngữ tự nhiên của bài toán hơn.

Kết nối với DP

Có một cách đọc dynamic programming đáng biết để dùng trong interview. Định nghĩa:

dp[i] = profit tối đa có thể đạt được nếu ngày bán là i

Thì:

dp[i] = prices[i] - min(prices[0], prices[1], ..., prices[i-1])

Đáp án là max(dp[0], dp[1], ..., dp[n-1]). Nhận thấy rằng tính mỗi dp[i] chỉ cần running minimum của mọi thứ trước đó — không cần lưu toàn bộ mảng dp. Đó là sự thu gọn O(1) space: biến min_price trong vòng lặp trên chính là running minimum đó, và max_profit tích lũy max qua tất cả dp[i]. Thuật toán single-pass là DP được tối ưu hóa không gian, và nhận ra kết nối đó giúp trong interview khi bạn có thể được hỏi "trước tiên hãy cho tôi thấy DP."

So sánh các approach

Cả hai approach đều dùng O(1) extra space — brute force chỉ cần biến đếm vòng lặp, optimal chỉ cần hai biến. Khoảng cách về time là thứ duy nhất quan trọng, và nó mang tính quyết định.

Edge cases

• Mảng một phần tử, ví dụ [5]: While loop bắt đầu với right = 1 và len = 1, nên right < len sai ngay. Trả về 0 mà không vào vòng lặp — không cần câu lệnh đặc biệt.
• Mảng giảm nghiêm ngặt, ví dụ [7,6,4,3,1]: Mỗi bước di chuyển L về phía trước vì giá mới luôn rẻ hơn. Nhánh else không bao giờ chạy. Trả về 0 — đúng, vì không giao dịch nào sinh lợi dương.
• Tất cả giá bằng nhau, ví dụ [3,3,3,3]: Mỗi prices[R] - prices[L] bằng 0, max_profit ở lại 0. Trả về 0.
• Mảng tăng nghiêm ngặt, ví dụ [1,2,3,4,5]: L không bao giờ rời index 0 vì không giá nào rẻ hơn giá đầu tiên. Profit tăng dần và đạt đỉnh 5 - 1 = 4 vào ngày cuối.
• Đỉnh ở giữa, ví dụ [1,9,1,9]: Sau khi L reset về index 2, cửa sổ thứ hai [1,9] cũng cho profit 8. Đáp án là 8, và thuật toán tìm thấy nó đúng.

Pattern: tối ưu hóa cặp có ràng buộc thứ tự

Hình dạng bài toán nên trigger giải pháp này: tìm cặp (arr[i], arr[j]) với i < j để tối đa hóa hàm nào đó của hai giá trị. Kỹ thuật luôn giống nhau — quét từ trái sang phải, duy trì running extreme ở phía trái, đánh giá phía phải tại mỗi vị trí. Running minimum không phải trick riêng cho giá cổ phiếu; đây là kỹ thuật chung cho mọi bài toán pair có ràng buộc thứ tự.

Keywords dẫn đến đây: "buy and sell," "single transaction," "maximum difference with order constraint," "you must buy before you sell."

Vị trí trong series

Đây là bài đầu tiên trong sliding window series vì nó có window đơn giản nhất có thể: không có ràng buộc size, không có character map, không có điều kiện shrink — chỉ là con trỏ trái nhảy về phía trước khi tìm thấy minimum mới. Mọi thứ trong series đều thêm một lớp phức tạp lên trên skeleton này.

• Longest Substring Without Repeating Characters (3): window vẫn có L và R, nhưng L phải co lại bất cứ khi nào một ký tự trùng lặp vào từ phía phải. Một hash map theo dõi vị trí ký tự. Điều kiện validity thay thế điều kiện "tìm thấy entry rẻ hơn."
• Longest Repeating Character Replacement (424): được phép thay thế tối đa k ký tự trong window. Khi nào di chuyển L phụ thuộc vào window_size - max_frequency > k.
• Minimum Window Substring (76): thay vì tối đa hóa, bạn tối thiểu hóa độ dài window theo ràng buộc coverage. L chỉ di chuyển khi window đã hợp lệ — ngược với hướng di chuyển pointer của bài này.

Lý do giải 121 trước tiên không phải vì xếp hạng độ khó mà vì mechanics rất thuần khiết. Một khi bạn thấy L và R di chuyển qua mảng giá với invariant rõ ràng, các bổ sung trong các bài trên dễ lập luận hơn nhiều.