Leetcode 188 Best Time to Buy and Sell Stock IV

Say you have an array for which the ith 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).

Solution 1: Use DP, local[i][j] is the max value sell at jth using i transaction. globe[i][j] is global best solution. No need to sell at day j. Space can be optimized to O(k). Also, if k>n/2 can apply fast calculation which is O(n) instead of O(n*k).

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     int n=prices.length;  
     if (k>n/2) return quickSolve(prices);  
     int[] local=new int[k+1];  
     int[] globe=new int[k+1];  
     for (int j=1; j<n; j++) {  
       int pre=0;  
       for (int i=1; i<=k; i++) {  
         int temp=globe[i];  
         local[i]=Math.max(pre,local[i]+prices[j]-prices[j-1]);  
         globe[i]=Math.max(globe[i],local[i]);  
         pre=temp;  
       }  
     }  
     return globe[k];  
   }  
   private int quickSolve(int[] prices) {  
     int res=0;  
     for (int i=1; i<prices.length; i++)  
       if (prices[i]>prices[i-1]) res+=prices[i]-prices[i-1];  
     return res;  
   }  
 }