I've got a DP solution.It can solved by O(kn).

First,describe the struture of the optimum solution.We can use t[i][j] to indicate the max profit of j day which have happend i times transactions.

We can recursively define the expression of t(i,j) like this:

**t[i][j]=max{ t[i][j-1], prices[j]-prices[j-1]+t[i-1][j-1]}.**

```
public class Solution {
public int maxProfit(int k, int[] prices) {
int n=prices.length;
int[][] t=new int[k+1][n];
for(int i=0;i<=k;i++){
t[k][0]=0;
}
for(int i=0;i<n;i++){
t[0][i]=0;
}
for(int i=1;i<=k;i++){
for(int j=1;j<n;j++){
t[i][j]=Math.max(t[i][j-1],prices[j]-prices[j-1]+t[i-1][j-1]);
}
}
return t[k][n-1];
}
```

}