text: /*
   * @lc app=leetcode id=188 lang=cpp
   *
   * [188] Best Time to Buy and Sell Stock IV
   */
  
  // @lc code=start
  class Solution {
  public:
      int maxProfit(int k, vector<int>& prices) {
          // version 4 in https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution
          if (prices.size() <= 1) return 0;
          vector<int> dp(k+1, 0);
          vector<int> minimum(k+1, prices[0]);
          for (int i = 1; i < prices.size(); i++) {
              for (int j = 1; j <= k; j++) {
                  minimum[j] = min(minimum[j], prices[i]-dp[j-1]);
                  dp[j] = max(dp[j], prices[i]-minimum[j]);
              }
          }
          return dp[k];
      }
  };
  // @lc code=end
  
  