Description Link to heading

121.best-time-to-buy-and-sell-stock

Solution Link to heading

dynamic programming Link to heading

dp[i] denotes maximum profit in first i days, so the recurrence relation of dp[i] is: dp[i] = min(dp[i - 1], a[i - 1] - min(price[0, i - 1)), 0).

greedy algorithm Link to heading

Let’s use cur to record the minimum element and replace the value of cur if the element is smaller, if the element is larger than cur, calculate the profit, save the maximum profit.

Code Link to heading 

class Solution {
  private:
    int min(int a, int b) {
        return a < b ? a : b;
    }
    int max(int a, int b, int c) {
        if (a > b)
            return a > c ? a : c;
        else
            return b > c ? b : c;
    }

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