## DEV Community

Prashant Mishra

Posted on

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
int max = Integer.MIN_VALUE;
int sell = 0;
-prices[index] + mProfit(index+1,1,prices),
mProfit(index+1,0,prices)
);
}
sell = Integer.max(
prices[index] + mProfit(index+1,2,prices),
mProfit(index+1,1,prices)
);
}
}
}
``````

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
int sell = 0;
-prices[index] + mProfit(index+1,1,prices,dp),
mProfit(index+1,0,prices,dp)
);
}
sell = Integer.max(
prices[index] + mProfit(index+1,2,prices,dp),
mProfit(index+1,1,prices,dp)
);
}
}
}
``````

Best approach:
In a way this is also dp:

``````class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int maxProfit = 0;
for( int i = 0;i< prices.length;i++){