LeetCode 121. Best Time to Buy and Sell Stock [Easy] [C++] 解題筆記

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

想法:

    從頭遍歷，不斷更新左邊最小的值 left_min，並計算根據當前的 left_min 計算目前的價差，並更新目前的

最大價差。

Complexity: O(n) time.

完整程式碼:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) { return 0; }
        int left_min = prices[0];
        int max_profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            left_min = min(prices[i], left_min);
            max_profit = max(max_profit, prices[i] - left_min);
        }
        return max_profit;
    }
};