This method is derived from III question and II question

```
// O(kn) O(k)
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() < 2 || k < 1) return 0;
if (k > prices.size() / 2) return greedy(prices);
vector<int> buy(k, INT_MIN), sell(k, 0);
for (auto p : prices) {
buy[0] = max(buy[0], -p);
sell[0] = max(sell[0], buy[0] + p);
for (int i = 1; i < k; i++) {
buy[i] = max(buy[i], sell[i - 1] - p);
sell[i] = max(sell[i], buy[i] + p);
}
}
return sell[k - 1];
}
private:
int greedy(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
profit += (prices[i] > prices[i - 1]) ? (prices[i] - prices[i - 1]) : 0;
}
return profit;
}
};
```