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)