Description Link to heading

122.best-time-to-buy-and-sell-stock-ii

Solution Link to heading

The key point of this problem is to find the recurrence formula of dp[i]. Let’s discuss this problem in two cases.

  • if prices[i - 1] is not selected, then dp[i] = dp[i - 1]. It shows that: prices[i - 1] < prices[i - 2];
  • if prices[i - 1] is selected, then prices[i - 1] >= prices[i - 2], dp[i] = dp[i - 1] + prices[i - 1] - prices[i - 2].

Code Link to heading 

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