Categories
Interview Questions

Best Time to Buy and Sell Stock with K transaction

The original question can be found here

Lets start from an elegant the solution :

				
					class Solution {
    public int maxProfit(int k,int[] prices) {
        if (prices.length<2 || k==0) return 0;
        
        int[] profits = new int[k+1];
        
        int[] balance = new int[k];
        Arrays.fill(balance,-prices[0]);
        
        for (int p : prices) {
            for (int i=0;i<k;i++) {
                balance[i] = Math.max(balance[i],profits[i]-p);
                profits[i+1] = Math.max(profits[i+1],p+balance[i]);
            }
        }
        return profits[k];
    }
}
				
			

This solution would run in O(n*k). if we dont mind getting our hands dirty, it can be better implemented and then explained like that:

				
					class Solution {
    public int maxProfit(int k,int[] prices) {
        if (prices.length<2 || k==0) return 0;
        
        int[] profits = new int[k+1];
        
        int[] balance = new int[k];
        balance[0]=-prices[0];
        
        int transactions=1;
        
        for (int p : prices) {

            if (transactions<k && profits[transactions]>profits[transactions-1]) {
                balance[transactions]=profits[transactions]-p;
                transactions++;
            }
                
            for (int i=0;i<transactions;i++) {
                balance[i] = Math.max(balance[i],profits[i]-p);
                profits[i+1] = Math.max(profits[i+1],p+balance[i]);
            }
        }
        return profits[transactions];
    }
}
				
			
Now it would run in O(n*m) where is the trade count in the optimal solution. commonly m<<k. 
 
Lets begin with the explanation, We’ll keep track of the following loop invariants:
 
  • profits[i] will hold the max profit we can get for i efficient full transactions.

profits[0] is always 0 since that’s the profit when we make no transactions, profits[1] is the maximal profit we could have with 1 efficient full transaction and so on.

  • balance[i] will hold the optimal balance we would have if we do i efficient full transactions and then an efficient buy.

since we have only have a buy for balance[0], it will eventually hold the negate of the minimal price, balance[1] will be the best balance after doing one full transaction efficiently and followed by a buy, and so on.

Whenever we find that profits[i]>profits[i-1]  it would mean that we can increase our profits by doing one more full transaction after i-1 efficient full transactions, so we search for this to hold, and when it does we start to work on profits for next i.

We try to maximize our balance[i] which consists of the profits[i] which is the profit we made so far, and paying for our following buy. for every new price we examine if we improve our balance when buying at that price, if we don’t we stay with the previous balance.

Then for profits[i+1] we take the optimal balance[i] and we need to add the price we get if we sell to complete the i+1 trade transaction, we will not do the sell if we previously had a better setup.

Eventually we return profits[transaction] which is the max profit for the optimal count of transactions.

 

Leave a Reply

Your email address will not be published. Required fields are marked *