Friday, March 20, 2015

188. Best Time to Buy and Sell Stock IV Leetcode Java

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:
Actually, in problem 123.Best Time to Buy and Sell Stock III, I already solved this problem. So please see that problem for full analysis. Basically, this is the general problem of all buy and sell stock problems. The trick part for any k transactions is that if k>prices.length/2, which basically means we can do as many as transactions for all n days.Because there is no meaning for buying and selling the stock on the same day, buy and sell on different days, which makes when k> length/2, it is the same as problem 122. Best Time to Buy and Sell Stock II. Other than that it is the same as problem 123. 
All relevant problems:
 public int maxProfit(int k, int[] prices) {  
    if(prices==null || prices.length==0 || k==0) return 0;  
    if(k>=prices.length/2){  
      int res=0;  
      for(int i=1;i<prices.length;i++){  
        res+=Math.max(prices[i]-prices[i-1],0);  
      }  
      return res;  
    }  
    int[] local=new int[k+1];
     int[] global=new int[k+1];
     int res=0;
     for(int i=1;i<prices.length;i++){
         for(int j=1;j<=k;j++){
             local[j]=Math.max(local[j]+prices[i]-prices[i-1],global[j-1]);
             global[j]=Math.max(global[j],local[j]);
             res=Math.max(res,global[j]);
         }
     }
     return res;
   }  

No comments:

Post a Comment