```
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
// Nothing to sell
if (n <= 1) return 0;
// Avoid using too many memory
if (k > n / 2) {
int ret = 0;
for (int i = 1; i < n; i++) {
ret += max(prices[i] - prices[i - 1], 0);
}
return ret;
}
// Here we use the general dp solution, with one dimension array
// Fill the table bottom-up
int l[k + 1] = {0};
int g[k + 1] = {0};
int gtemp = 0;
for (int i = 1; i < n; i++) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; j++) {
l[j] = max(gtemp + max(diff, 0), l[j] + diff);
gtemp = j == k ? 0 : g[j];
g[j] = max(l[j], g[j]);
}
}
return g[k];
}
```