✔✔All "Best Time To Buy and Sell Stock Based Solutions"|| Recursive To Space Optimized
Anonymous User
203
Stock DP:
This document consist all the major problems of "Best Time to Buy and Sell Stocks" .
I have discussed all the approach from recursion ➡ DP Top Down ➡ DP Bottom Up ➡ Space Optimization in DP. If you notice in all the program that there is minimal change in the code and you can do it with only looking at one approach of every program.
Hope it helps.
1. Best Time to Buy and Sell Stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans=INT_MIN,maxi=INT_MIN;
for(int i=prices.size()-1;i>=0;i--)
{
maxi=max(maxi,prices[i]);
ans=max(ans,maxi-prices[i]);
}
return ans;
}
};2. Best Time to Buy and Sell Stock II
Recursive Method:
class Solution {
public:
int helper(vector <int> &prices,int index,bool isBuy)
{
if(index==prices.size())
return 0;
if(isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return max(-prices[index]+helper(prices,index+1,0),helper(prices,index+1,1));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return max(prices[index]+helper(prices,index+1,1),helper(prices,index+1,0));
}
}
int maxProfit(vector<int>& prices) {
bool buy=true;
return helper(prices,0,buy);
}
};Memoization:
class Solution {
public:
int helper(vector <int> &prices,int index,bool isBuy,vector <vector <int>> &dp)
{
if(index==prices.size())
return 0;
if(dp[index][isBuy]!=-1)
return dp[index][isBuy];
if(isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return dp[index][isBuy]=max(-prices[index]+helper(prices,index+1,0,dp),helper(prices,index+1,1,dp));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return dp[index][isBuy]=max(prices[index]+helper(prices,index+1,1,dp),helper(prices,index+1,0,dp));
}
}
int maxProfit(vector<int>& prices) {
bool buy=true;
vector <vector <int>> dp(prices.size()+1,vector <int> (2,-1));
return helper(prices,0,buy,dp);
}
};Iterative DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector <vector <int>> dp(prices.size()+1,vector <int> (2));
dp[n][0]=0;
dp[n][1]=0;
// index => n-1 to 0
// isBuy => 0 to 1
for(int index=n-1;index>=0;index--)
{
for(int isBuy=0;isBuy<2;isBuy++)
{
if(isBuy)
{
// either buy and find the great day for sell or not to buy on that day
dp[index][isBuy]=max(-prices[index]+dp[index+1][0],dp[index+1][1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
dp[index][isBuy]=max(prices[index]+dp[index+1][1],dp[index+1][0]);
}
}
}
return dp[0][1];
}
};Space Optimization
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector <int> after(2),curr(2);
after[0]=0;
after[1]=0;
// index => n-1 to 0
// isBuy => 0 to 1
for(int index=n-1;index>=0;index--)
{
for(int isBuy=0;isBuy<2;isBuy++)
{
if(isBuy)
{
// either buy and find the great day for sell or not to buy on that day
curr[isBuy]=max(-prices[index]+after[0],after[1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
curr[isBuy]=max(prices[index]+after[1],after[0]);
}
}
curr=after;
}
return curr[1];
}
};3. Best Time to Buy and Sell Stock III
Recursive
class Solution {
public:
int helper(vector <int> &prices, int index,bool isBuy,int atmost)
{
if(atmost==0) // can't do any further transactions
return 0;
if(index==prices.size())
return 0;
if(isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return max(-prices[index]+helper(prices,index+1,0,atmost),helper(prices,index+1,1,atmost));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return max(prices[index]+helper(prices,index+1,1,atmost-1),helper(prices,index+1,0,atmost));
}
}
int maxProfit(vector<int>& prices) {
bool isBuy=true;
return helper(prices,0,isBuy,2);
}
};Memoization
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, int atmost, vector<vector<vector<int>>> &dp)
{
if (atmost == 0) // can't do any further transactions
return 0;
if (index == prices.size())
return 0;
if (dp[index][atmost][isBuy] != -1)
return dp[index][atmost][isBuy];
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return dp[index][atmost][isBuy] = max(-prices[index] + helper(prices, index + 1, 0, atmost, dp), helper(prices, index + 1, 1, atmost, dp));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return dp[index][atmost][isBuy] = max(prices[index] + helper(prices, index + 1, 1, atmost - 1, dp), helper(prices, index + 1, 0, atmost, dp));
}
}
int maxProfit(vector<int> &prices)
{
bool isBuy = true;
int n = prices.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(3, vector<int>(2, -1)));
return helper(prices, 0, isBuy, 2, dp);
}
};Iterative DP
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(3, vector<int>(2, 0)));
for (int index = n - 1; index >= 0; index--)
{
for (int atmost = 1; atmost < 3; atmost++)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
dp[index][atmost][isBuy] = max(-prices[index] + dp[index + 1][atmost][0], dp[index + 1][atmost][1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
dp[index][atmost][isBuy] = max(prices[index] + dp[index + 1][atmost - 1][1], dp[index + 1][atmost][0]);
}
}
}
}
return dp[0][2][1];
}
};Space Optimization
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(3, vector<int>(2, 0)));
vector <vector <int>> after(3,vector <int> (2,0)),curr(3,vector <int> (2,0));
for (int index = n - 1; index >= 0; index--)
{
for (int atmost = 1; atmost < 3; atmost++)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
curr[atmost][isBuy] = max(-prices[index] + after[atmost][0], after[atmost][1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
curr[atmost][isBuy] = max(prices[index] + after[atmost - 1][1], after[atmost][0]);
}
}
}
after=curr;
}
return curr[2][1];
}
};4. Best Time to Buy and Sell Stock IV
Recursive
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, int atmost)
{
if (atmost == 0) // can't do any further transactions
return 0;
if (index == prices.size())
return 0;
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return max(-prices[index] + helper(prices, index + 1, 0, atmost), helper(prices, index + 1, 1, atmost));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return max(prices[index] + helper(prices, index + 1, 1, atmost - 1), helper(prices, index + 1, 0, atmost));
}
}
int maxProfit(int k, vector<int> &prices)
{
bool isBuy = true;
return helper(prices, 0, isBuy, k);
}
};Memoization
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, int atmost, vector<vector<vector<int>>> &dp)
{
if (atmost == 0) // can't do any further transactions
return 0;
if (index == prices.size())
return 0;
if (dp[index][atmost][isBuy] != -1)
return dp[index][atmost][isBuy];
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return dp[index][atmost][isBuy] = max(-prices[index] + helper(prices, index + 1, 0, atmost, dp), helper(prices, index + 1, 1, atmost, dp));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return dp[index][atmost][isBuy] = max(prices[index] + helper(prices, index + 1, 1, atmost - 1, dp), helper(prices, index + 1, 0, atmost, dp));
}
}
int maxProfit(int k, vector<int> &prices)
{
bool isBuy = true;
int n = prices.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, -1)));
return helper(prices, 0, isBuy, k, dp);
}
};Iterative
class Solution
{
public:
int maxProfit(int k, vector<int> &prices)
{
int n = prices.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
for (int index = n - 1; index >= 0; index--)
{
for (int atmost = 1; atmost <= k; atmost++)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
dp[index][atmost][isBuy] = max(-prices[index] + dp[index + 1][atmost][0], dp[index + 1][atmost][1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
dp[index][atmost][isBuy] = max(prices[index] + dp[index + 1][atmost - 1][1], dp[index + 1][atmost][0]);
}
}
}
}
return dp[0][k][1];
}
};Space Optimized
class Solution
{
public:
int maxProfit(int k, vector<int> &prices)
{
int n = prices.size();
vector<vector<int>> after(k + 1, vector<int>(2, 0)), curr(k + 1, vector<int>(2, 0));
for (int index = n - 1; index >= 0; index--)
{
for (int atmost = 1; atmost <= k; atmost++)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
curr[atmost][isBuy] = max(-prices[index] + after[atmost][0], after[atmost][1]);
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
curr[atmost][isBuy] = max(prices[index] + after[atmost - 1][1], after[atmost][0]);
}
}
}
after = curr;
}
return curr[k][1];
}
};5. Best Time to Buy and Sell Stock with Cooldown
Recursive
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy)
{
if (index >= prices.size())
return 0;
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return max(-prices[index] + helper(prices, index + 1, 0), helper(prices, index + 1, 1));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return max(prices[index] + helper(prices, index + 2, 1), helper(prices, index + 1, 0));
}
}
int maxProfit(vector<int> &prices)
{
bool buy = true;
return helper(prices, 0, buy);
}
};Memoization
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, vector<vector<int>> &dp)
{
if (index >= prices.size())
return 0;
if (dp[index][isBuy] != -1)
return dp[index][isBuy];
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return dp[index][isBuy] = max(-prices[index] + helper(prices, index + 1, 0, dp), helper(prices, index + 1, 1, dp));
}
else
{
// either sell and find the next greate day to buy oe not to sell on that day
return dp[index][isBuy] = max(prices[index] + helper(prices, index + 2, 1, dp), helper(prices, index + 1, 0, dp));
}
};
int maxProfit(vector<int> &prices)
{
bool buy = true;
vector<vector<int>> dp(prices.size() + 1, vector<int>(2, -1));
return helper(prices, 0, buy, dp);
}
};Iterative DP
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size();
vector<vector<int>> dp(n + 2, vector<int>(2));
dp[n][0] = 0;
dp[n][1] = 0;
// index => n-1 to 0
// isBuy => 0 to 1
for (int index = n - 1; index >= 0; index--)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
dp[index][isBuy] = max(-prices[index] + dp[index + 1][0], dp[index + 1][1]);
}
else
{
// either sell and find the next great day to buy (not to take next day in consideration)
// or not to sell on that day
dp[index][isBuy] = max(prices[index] + dp[index + 2][1], dp[index + 1][0]);
}
}
}
return dp[0][1];
}
};6. Best Time to Buy and Sell Stock with Transaction fee
Recursive
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, int fee)
{
if (index >= prices.size())
return 0;
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return max(-prices[index] + helper(prices, index + 1, 0, fee), helper(prices, index + 1, 1, fee));
}
else
{
// either sell and find the next greate day to buy or not to sell on that day
return max(prices[index] - fee + helper(prices, index + 1, 1, fee), helper(prices, index + 1, 0, fee));
}
}
int maxProfit(vector<int> &prices, int fee)
{
bool buy = true;
return helper(prices, 0, buy, fee);
}
};Memoization
class Solution
{
public:
int helper(vector<int> &prices, int index, bool isBuy, int &fee, vector<vector<int>> &dp)
{
if (index >= prices.size())
return 0;
if (dp[index][isBuy] != -1)
return dp[index][isBuy];
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
return dp[index][isBuy] = max(-prices[index] + helper(prices, index + 1, 0, fee, dp), helper(prices, index + 1, 1, fee, dp));
}
else
{
// either sell and pay fee and find the next greate day to buy or not to sell on that day
return dp[index][isBuy] = max(prices[index] - fee + helper(prices, index + 1, 1, fee, dp), helper(prices, index + 1, 0, fee, dp));
}
}
int maxProfit(vector<int> &prices, int fee)
{
bool buy = true;
vector<vector<int>> dp(prices.size() + 1, vector<int>(2, -1));
return helper(prices, 0, buy, fee, dp);
}
};Iterative DP
class Solution
{
public:
int maxProfit(vector<int> &prices, int fee)
{
int n = prices.size();
vector<vector<int>> dp(n + 2, vector<int>(2));
dp[n][0] = 0;
dp[n][1] = 0;
// index => n-1 to 0
// isBuy => 0 to 1
for (int index = n - 1; index >= 0; index--)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
dp[index][isBuy] = max(-prices[index] + dp[index + 1][0], dp[index + 1][1]);
}
else
{
// either sell and find the next great day to buy and pay fee
// or not to sell on that day
dp[index][isBuy] = max(prices[index] - fee + dp[index + 1][1], dp[index + 1][0]);
}
}
}
return dp[0][1];
}
};Space Optimization
class Solution
{
public:
int maxProfit(vector<int> &prices, int fee)
{
int n = prices.size();
vector<int> after(2), curr(2);
after[0] = 0;
after[1] = 0;
// index => n-1 to 0
// isBuy => 0 to 1
for (int index = n - 1; index >= 0; index--)
{
for (int isBuy = 0; isBuy < 2; isBuy++)
{
if (isBuy)
{
// either buy and find the great day for sell or not to buy on that day
curr[isBuy] = max(-prices[index] + after[0], after[1]);
}
else
{
// either sell and pay fee and find the next great day to buy or not to sell on that day
curr[isBuy] = max(prices[index] - fee + after[1], after[0]);
}
}
after = curr;
}
return curr[1];
}
};
Comments (0)