DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Buy and sell stocks

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)