[LeetCode] Best Time to Buy and Sell Stock IV

 1 class Solution {
 2 public:
 3     int maxProfit(int k, vector<int>& prices) {
 4         int n = prices.size();
 5         if (k >= n / 2) return quickProfit(prices);
 6         vector<vector<int> > dp(k + 1, vector<int>(n, 0));
 7         for (int i = 1; i <= k; i++) {
 8             int temp = dp[i - 1][0] - prices[0];
 9             for (int j = 1; j < n; j++) {
10                 dp[i][j] = max(dp[i][j - 1], prices[j] + temp);
11                 temp = max(temp, dp[i - 1][j] - prices[j]);
12             }
13         }
14         return dp[k][n - 1];
15     }
16 private:
17     int quickProfit(vector<int>& prices) {
18         int n = prices.size(), profit = 0;
19         for (int i = 1; i < n; i++)
20             if (prices[i] > prices[i - 1])
21                 profit += prices[i] - prices[i - 1];
22         return profit;
23     }
24 };