# 121 - Best Time to Buy and Sell Stock

解法一 - DP

這題的解題思路如下：

1. 先定義 DP[i] 表示到第 i 天的 max profit

2. 那 DP[i] = max(0, DP[i-1] + price[i] - price[i-1])

   為什麼是這樣的公式，請見下圖：

   
3. 第 1 天不可能賺錢，所以初始化 DP[0] = 0

實作出來的程式碼如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;

        vector<int> dp(prices.size());
        dp[0] = 0;

        int maxVal = dp[0];

        for(int i=1; i<dp.size(); i++) {
            dp[i] = max(0, dp[i-1]+prices[i]-prices[i-1]);
            if(dp[i] > maxVal) maxVal = dp[i];
        }

        return maxVal;
    }
};

解法二 - DP

我們可以用一個 DP array 來儲存在第 i 天可以賺到的最大 profit，所以

DP[i] = price[i] - 從第 0 天到第 i-1 天看到的最低價格。

至於從第 0 天到第 i-1 天的最低價格，我們可以先存在 low_price array 中，實作如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;

        int n = prices.size();
        vector<int> low_price(n);
        vector<int> great_profit(n);

        low_price[0] = prices[0];
        great_profit[0] = 0;
        for(int i = 1; i < n; ++i) {
            low_price[i] = min(low_price[i-1], prices[i]);
            great_profit[i] = max(great_profit[i-1], prices[i] - low_price[i-1]);
        }

        return great_profit[n-1];
    }
};

解法三 - 解法二的 DP 優化

解法二有一個冗餘的地方是我們用了一個 array 來儲存從第 0 天到第 i-1 天的最低價格，其實可以只用一個變數來存。因為我們是從前往後走過整個 prices array，所以我們看 low_price 時，

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;

        int n = prices.size();
        int low_price = prices[0];
        vector<int> great_profit(n);

        great_profit[0] = 0;
        for(int i = 1; i < n; ++i) {
            low_price = min(low_price, prices[i]);
            great_profit[i] = max(great_profit[i-1], prices[i] - low_price);
        }

        return great_profit[n-1];
    }
};

解法四 - 解法三的 DP 優化

其實解法三裡面的 DP array 也可以不需要，所以就可以變得更簡潔。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low_price = numeric_limits<int>::max();
        int great_profit = 0;

        for(int i = 0; i < prices.size(); ++i) {
            low_price = min(low_price, prices[i]);
            great_profit = max(great_profit, prices[i] - low_price);
        }

        return great_profit;
    }
};

解法五 - Divide & Conquer

參考：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/39206/O(n)-solution-without-using-DP.-Using-Divide-and-Conquer-technique

概念：每次都把 array 分成兩半，然後 recursively 地繼續 divide array，直到遇到 base case（只剩 1 個 element）才回傳。

然後要 merge 時，考慮左半 array 的最小值跟右半 array 的最大值，就可以算出這兩個合併起來的 max profit，另外還需要把這兩個 array 合起來後的最小值跟最大值往上傳，更上面才能 merge，實作如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return prices.size() > 0 ? helper(prices, 0, prices.size() -1)[0] : 0;
    }

private:
    /**
     * index 0: max profit, index 1: max price in the range and index 2: min price in the range
     */
    vector<int> helper(const vector<int>& prices, int i, int j) {
        // Base case
        vector<int> result = {0, prices[i], prices[j]};
        if(i == j) return result;

        int m = i + (j - i) / 2;
        vector<int> left = helper(prices, i, m);
        vector<int> right = helper(prices, m+1, j);
        result[0] = max(left[0], max(right[0], right[1] - left[2]));
        result[1] = max(left[1], right[1]);
        result[2] = min(left[2], right[2]);

        return result;
    }
};