Best Time to Buy and Sell Stock IV

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way: As shown in best-time-to-buy-and-sell-stock-iii. There exists a DP solution within O(nk) run time and space.

The basic logic is
opt[i, j] // the maximum profit using i transactions in j days
// base case
opt[0, j] = 0 for all j
opt[i, 0] = 0 for all i
// iteration
opt[i, j] = max(opt[i, j-1], opt[i-1,t] + p[j] - p[t+1]) for 0<=t < j

However, this algorithm using gets TLE.

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     // edge case  
     if(k > prices.length/2) k= prices.length/2;
     if(prices.length==0) return 0;  
     // DP  
     int opt[][] = new int[k+1][prices.length+1];  
     // base case  
     for(int i = 0;i <= k;i++) opt[i][0] = 0;  
     for(int j = 0;j <= prices.length;j++) opt[0][j] = 0;  
     // iteration  
     for(int i = 1;i <= k;i++){  
       int t = opt[i-1][0] - prices[0];  
       for(int j = 1;j <= prices.length;j++){  
         opt[i][j] = Math.max(opt[i][j-1], t + prices[j-1]);  
         if(j < prices.length) t = Math.max(t, opt[i-1][j] - prices[j]);  
       }  
     }  
     return opt[k][prices.length];  
   }  
 }  

I don't know why this gets TLE, because this is already a high-efficiency algorithm. I saw the Discuss, some one put forward a great idea adding optimization for it. It is when k >= prices.length/2, that means we can make as many transactions as we can, that brings us the problem back to best-time-to-buy-and-sell-stock-ii which can be simply solve in O(n) using a greedy approach. That helps narrow down a lot of tests case to O(n) run time.

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     // edge case  
     if(k > prices.length/2){  
       int sum = 0;  
       for(int i = 1;i < prices.length;i++)  
         sum += Math.max(prices[i] - prices[i-1],0);  
       return sum;  
     }  
     if(prices.length==0) return 0;  
     // DP  
     int opt[][] = new int[k+1][prices.length+1];  
     // base case  
     for(int i = 0;i <= k;i++) opt[i][0] = 0;  
     for(int j = 0;j <= prices.length;j++) opt[0][j] = 0;  
     // iteration  
     for(int i = 1;i <= k;i++){  
       int t = opt[i-1][0] - prices[0];  
       for(int j = 1;j <= prices.length;j++){  
         opt[i][j] = Math.max(opt[i][j-1], t + prices[j-1]);  
         if(j < prices.length) t = Math.max(t, opt[i-1][j] - prices[j]);  
       }  
     }  
     return opt[k][prices.length];  
   }  
 }  

Improved Way: Is there a solution better than O(kn)? There is a post using O(n+klogn) run time and O(n) space. It's idea is first find all useful valley-peak pairs and then merge them into k pairs.

https://oj.leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack