Buy and sell stocks
this will lead to TLE:
TC: exponential as we will be recursively calling the mProfit method, sc: recursive stack space
class Solution { public int maxProfit(int[] prices) { return mProfit(0,0,prices); } public int mProfit(int index ,int canBuy, int[] prices){ //base case if(index==prices.length || canBuy==2) return 0; int max = Integer.MIN_VALUE; int buy = 0; int sell = 0; if(canBuy==0){ buy = Integer.max( -prices[index] + mProfit(index+1,1,prices), mProfit(index+1,0,prices) ); } if(canBuy==1){ sell = Integer.max( prices[index] + mProfit(index+1,2,prices), mProfit(index+1,1,prices) ); } return Integer.max(buy,sell); } } DP approach:
TC: O(n*2) and there will be O(N*2) times the method will get called (mProfit)
SC: O(N*2) + O(N) for the dp array and the recursive stack space
class Solution { public int maxProfit(int[] prices) { int dp[][] = new int[prices.length][2]; for(int d[] : dp){ Arrays.fill(d,-1); } return mProfit(0,0,prices,dp); } public int mProfit(int index ,int canBuy, int[] prices,int dp[][]){ //base case if(index==prices.length || canBuy==2) return 0; if(dp[index][canBuy]!=-1) return dp[index][canBuy]; int buy = 0; int sell = 0; if(canBuy==0){ buy = Integer.max( -prices[index] + mProfit(index+1,1,prices,dp), mProfit(index+1,0,prices,dp) ); } if(canBuy==1){ sell = Integer.max( prices[index] + mProfit(index+1,2,prices,dp), mProfit(index+1,1,prices,dp) ); } return dp[index][canBuy] = Integer.max(buy,sell); } } Best approach:
In a way this is also dp:
class Solution { public int maxProfit(int[] prices) { int buyPrice = Integer.MAX_VALUE; int profit = 0; int maxProfit = 0; for( int i = 0;i< prices.length;i++){ if(prices[i] < buyPrice){ buyPrice = prices[i]; } profit =prices[i]- buyPrice; if( profit > maxProfit) { maxProfit = profit; } } return maxProfit; } } 
Top comments (0)