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
👋 Kindness is contagious

Please leave your appreciation by commenting on this post!

It takes one minute and is worth it for your career.

Get started

Thank you!

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay