在 LeetCode 121 題「Best Time to Buy and Sell Stock」中，我們需要找到一個最佳的買入和賣出時間，使得我們可以從股價變動中獲得最大的利潤。這題的關鍵點在於如何有效地找到這樣的兩個時間點來達到最大化的收益。

題目：
給定一個陣列，其中第 i 個元素代表某天的股價。我們只允許執行一次買入和一次賣出操作，並且要求賣出時間必須晚於買入時間。目標是計算最大的可能利潤。如果無法實現任何利潤（即股價持續下跌），則回傳 0。

範例：

輸入: [7, 1, 5, 3, 6, 4]
輸出: 5
解釋: 在價格為 1 時買入，並在價格為 6 時賣出，利潤為 6-1=5。
注意利潤必須在買入前進行。

解題思路

這道題目是典型的「找最大差值」問題。我們只需找到股價最低點作為買入時機，再在之後的時間中找到最高的賣出時機，計算兩者的差值，並追蹤最大的利潤。

• 在遍歷股價的過程中，我們需要同時記錄當前遍歷過的最低股價，並在每一步比較當天的價格與這個最低股價來計算潛在的利潤。
• 因為我們的賣出時間必須在買入時間之後，所以每一步的價格比較都基於已知的最小股價（也就是我們遍歷過的最小值）。

解法

使用一個迴圈單次遍歷的方式來解決這個問題，時間複雜度為 O(n)。步驟如下：

1. 設定變數 min_price 來追蹤目前出現過的最低股價。
2. 設定變數 max_profit 來追蹤目前為止可以達到的最大利潤。
3. 遍歷股價清單，對於每一個股價：
   • 如果當前股價比 min_price 還低，則更新 min_price 為當前股價。
   • 否則計算以當前股價賣出時的利潤（即當前股價減去 min_price），並更新 max_profit。
4. 最後的 max_profit 就是最大利潤。

實作：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        int minPrice = INT_MAX;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] < minPrice)
                minPrice = prices[i];
            else
                maxProfit = max(maxProfit, prices[i]-minPrice);
        }
        return maxProfit;
    }
};

補充
這題用DP來解，也有看到有人用 Sliding Window 來解。