```
public int maxProfit(int k, int[] prices) {
if (prices==null) return 0;
int len = prices.length;
// One transaction takes two steps: buy and sell. So k * 2 >= len means we can complete unlimited transactions.
if (k * 2 >= len) {
int max = 0;
for (int i = 1; i < prices.length; i++)
if (prices[i] - prices[i - 1] > 0)
max += prices[i] - prices[i - 1];
return max;
}
// max[i][j]: Maximum profit for i prices with j transactions
int max[][] = new int[len][k+1];
for (int j = 1; j <= k; j++) {
// maxLeftMoneyWithUnsoldStock : Maximum left money in hand, with the stock unsold.
int maxLeftMoneyWithUnsoldStock = -prices[0];
for (int i = 1; i < len; i++) {
// 1) max[i-1][j]: Already finished j transactions in i - 1 time;
// 2) maxLeftMoneyWithUnsoldStock + prices[i] : sell the stock this time.
max[i][j] = Math.max(max[i-1][j], maxLeftMoneyWithUnsoldStock + prices[i]);
maxLeftMoneyWithUnsoldStock = Math.max(maxLeftMoneyWithUnsoldStock, max[i-1][j-1] - prices[i]);
}
}
return max[len-1][k];
}
```