DP 36. Buy and Sell Stock - II | Recursion to Space Optimisation
ฝัง
- เผยแพร่เมื่อ 24 มี.ค. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3nYO17H
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Buy and Sell Stock II.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![[TH] Esports World Cup : Grand Final](http://i.ytimg.com/vi/sedbKhFYDMo/mqdefault.jpg)
Shall we Bow Down, yeah he is a KING.
Guys, along with this dp approach, greedy also works in this problem.
If you are curious:
If the stock price of tomorrow is greater than today, buy it today and sell it tomorrow. (it is as greedy as it can be.)
sum of all the profit is automatically the maximum profit anyone can get.
sum = 0
for i in range(1, len(prices)):
sum += (prices[i] - prices[i-1]) if prices[i] >= prices[i-1] else 0
return sum
thank you for explaining how greedy works here. greedy is indeed tougher than dp as it is tougher to get through observation that greedy will work.
@@Dontpushyour_luck for recognizing the greedy can be used or not what I try to do is plot on a paper the numbers in the array or similar things and then if on sudden increase or decrease something happen then it gives a possibility of greedy>
So far this approach has worked for me as here also while increasing do nothing the moment it decreases you need to sell it
@@priyansh8656 can you elaborate this intuition more ?
Don't understand how greedy will be correct here.. If let's say there's an array [5,3,8], then buying stock on the first index(price=5) itself is a worse decision than buying stock on 2nd index(price=3) since in both cases the selling price will be 8 but the buying price is different?
@@siddharthchauhan961 Greedy is applied on consecutive days. So only when successive day is larger than previous day we mark it as profit. In you example we will compare 5,3 since 3 is smaller we'll skip this iteration then we'll compare 3,8 since 8 is larger we'll count different as profit.
Hope this helps.
In my entire life, I'll always remember this special guy. Always.
bro you are from which batch ?
i dont know how long my journey will go but for sure you are the best teacher ever❤❤
The Best 💫
Good effort to link the (more general) recursive approach to DP to 4 variable approach. But this problem can be solved from intuition in a very simple way using just 1 extra variable. Just compare today with yesterday and sell to make immediate profit (if today > yesterday). Keep doing so: profit += today - yesterday
yes ... I solved this Q previously in this way. At that time I had no idea of dp.
@@vimalslab3398 same bro!
yeah, greedy works great here
this is not intution , intution should have proof.
@@amandixit3555 Good point, at first, i also solved it without using recursion, but now i see, that isn't very logical and intuitive, its just a flick that greedy worked here.
Thankyou so much Striver for your awesome DP Playlist. I was able to solve all the 6 variants of DP on stocks starting from recursion to space optimization very easily in one shot and in less time as well. This playlist is top-notch and I have got good confidence now in DP. Keep up the good work. No one can teach at your level. You are the best ❤❤
UNDERSTOOD.....Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
what an amazing approach the final one😊
my approach of this question
int maxProfit(vector& a) {
int curr=a[0];
int profit=0;
for(int i=1;i
Great approach !!! TC = O(n) and SC= O(1).
I request Mr Striver to highlight this comment for everyone to see.
Thanks Striver, I just watched this video and did other variations on my own.
I am stuck with this problem for a few days, but after watching your video, I am able to solve the problem.
Thanks Bhaiya .
Brilliant teaching skills ..hats off
I WAS DOING THESE QUES FOR 2 WEEKS AND BY JUST SEEING THIS SINGLE VIDEO, I CAN DO ALL QUES ON STOCKS...THANKS A LOT
This is mind blowing🤯 .Understood sir thanks alot💙
Without watching your video, I solved this question on my own. Finally I am beginning to see through dp. I know I am yet a beginner in dp, but I shall learn dp so good that I would be able to do dp hard questions on codeforces. I know that it will be a long journey, but thank you for building my foundation so good. Dp is not intuitive at all but atleast for a beginning I am able to look into the intuition of dp.
How is your progress? :)
@@joshuamanivinod9873 pretty good. I have completed this playlist and now I am able to do dp without any fear. I am also able to understand solutions that others give for dp questions, whereas before I couldn't understand a bit of it.
Damn Striver, your lectures are helping me alot in solving such problems without the need of watching the entire video !! Watched this video till recursion part, and did solved this Question from memoization to space optimisation on my own😀😇 Thanks Alott
I am glad you explained the four variable solution, it was nightmare to understand that solution from discuss section.
I solve by myself till 2 array optimization.
UNDERSTOODDDDDDDD
You are commendable, the efforts you put in making these videos, helps us to understand clearly. You teach the concept, through which we can solve any problem!! Keep up the hard work, and thank you !! 🙏🙏🌸🌸
Understood, Indeed it was amazing
Striver, you don't even need the currBuy and currNotBuy variables. A great explanation, thanks for this DP series its really amazing.
The way you explain is wonderful. Thank you so much Striver. I get addicted to this series.
same bro . its like some kinda webseries that provides good dopomine
excellent logical way
Thanks for amazing solution striver
I got this in an Interview for a small Startup, could not solve it. As My whole DP Chapter was Pending. Thanks Striver ❤
Excellent explanation!!! Btw this can be solved without dp as well in O(n). Intuituion is similar, if we don't have stock we can only buy. If we have it we will update buy price if current value is lower than our buy price else we can sell it. While selling we'll keep going as long as we're getting higher value.
long getMaximumProfit(long *values, int n)
{
bool hasStock=false;
long buy=0,profit=0;
for(int i=0;i
ya , i thought for the greedy approach to just buy on the local minimas and sell it on local maximas
amazing explanation!
How on earth can anyone get this type of intution to solve this type of problem?? Each problem with its own unique style !! DP just blows my mind !! Hope that I might can solve this type of problem one day by my own !!
You don't know how much we all waited for this ❤️...Keep up the good work bhaiya...Good luck and have all our blessings 🥳
Good morning sir, Understood this problem very well.
Best explanation ever.
I solved this problem lot of times by seeing solution in discussion forms but never understood,
But today I understood this very well, never forgot this again.
Thank you so much.
Understood Thank you so much
What an explanation! Never imagined that this question could be converted to such easy algebraic technique!
Understoood , but afer watching it twice .
finally Hell lot ot effort requires to make and consume the video fruitfully.
😎😎😎😎😎😎
Understood! Also greedy solution is the best for this problem (C++ solution) -
TC - O(n) and SC - O(1)
long getMaximumProfit(long* values, int n)
{
if(n
Recurrence isnt required for this question either.
You can simply buy the stock on every day and sell it either on the same day if the next day has a lesser value or sell it next day and buy it again if it has a greater value.
Time Complexity-> O(N)
Space Complexity->O(1)
public class Solution {
public static long getMaximumProfit (int n, long[] values) {
if(n==0) return 0;
long total=0;
for(int i=1;i0)
total+=values[i]-values[i-1];
return total;
}
}
A much simpler approach
long profit = 0;
for(int i=0;i values[i]){
profit = profit + (values[i+1]-values[i]);
}
}
return profit;
Best TEacher Everr!!!
I don't know why this code works but... I think it is the most optimal code so far.
long profit=0;
for(int i=0;i
This is the greedy approch.
Institution is very simple : If the stock's price is increased tomorrow as compare to today, we will buy it and in last we will return our total sum
We can also do this with just using single 2 size array that we have learnt....... Thanks Striver
Understood sir !!🙏🙏
It can also be optimized to one array i.e two variables.
The way you have explained this is pretty awesome. Keep up the good work Raj bhai. Thank you once again.
Beautifully explained, cannot be better !!!
Understood
Also there is no need to carry cur array
It can be solved like the previous question easily too
class Solution {
public:
int maxProfit(vector& prices) {
int ans = 0;
int mini = prices[0];
int n = prices.size();
int profit;
int prev = mini;
for(int i = 1; i < n; i++)
{
profit = prices[i] - mini;
if(profit > 0)
ans = ans + profit;
mini = prices[i];
}
return ans;
}
};
You have no idea how eagerly I was waiting for videos
Striver you lied that it's one of best DP series available!
Its not one of Best its THE BEST.
Thanks a lot MAN.
Understood!
Thank you for your videos! I just found you and I'll def go over all of your videos but I have interviews coming up soon and need to understand the Memoization (optimization part) first. I'm wondering which video I should go for for memoization (optimization part)? is DP 1 intruduction video the right one? Thanks in advance.
thanku soo much for this nice playlist of dp .
OMG!!!!!!! excellent optimisation...👌👌
Solution's journey is very exciting , and yes I understood the problem.
Thank you very much for your efforts.
Really appreciate It sir
Understood Amazing!
But this works too
int maxProfit(vector& prices) {
int profit = 0;
int n = prices.size();
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
}
return profit;
}
understood!!
Understood!!!
You can also use greedy, it's more optimal in this problem, below is c++ code
int maxProfit(vector& prices) {
int profit = 0;
for(int i = 0; i < prices.size()-1; i++)
if(prices[i] < prices[i+1])
profit += prices[i+1] - prices[i];
return profit;
}
but how it works. Give some proofs as well
@@rishabhkumar8115 whenever you see that arr[i+1] is more than arr[i], consider trading, that's it.
@@tusharnain6652 but there is no uniformicity of data. there is possibility of getting more profite by selling current stock on other day after (i+1)th day.
@@rishabhkumar8115 yes, you're right.
Damn, they should add more testcases.
@@rishabhkumar8115 True there is a possibility of getting more profit by selling current stock on other say after (i+1)th day but that will still result in same net profit.
consider a case like [p1 p2 p3] where p1< p2
It's all about understanding this question and all of it's variations can be easily solved.
I have said it multiple times , its just about understanding recursive approach -> rest is literally cake walk down to the space optimization
This can be solved without dp
class Solution {
public:
#define loop(i, l, n) for (int i = l; i = n; i--)
int maxProfit(vector& prices)
{
int ans = 0;
int n = prices.size();
loop(i,1,n-1)
{
if(prices[i]>prices[i-1])
{
ans+=prices[i]-prices[i-1];
}
}
return ans;
}
};
Understoood
Fully understand !! 🔥
Thanks striver 😊😊
thankyou sir
Understood.
Can also be done with single array or just 2 variables.
understood 🙏
Understood :)
Here you can sell the stock and then you can buy the same stock on the same day(if it is less than the next stock price) i.e same index value act as the selling as well as buying.....correct me if i'm wrong
Understood !!!!!
26:33 Same thing I did in the last two lines. No Words❤🔥
Understood !!
@takeUforward
please explain the below code:-
class Solution {
public:
int maxProfit(vector& prices) {
int n=prices.size();
vector dp(2,0);
for(int ind=n-1;ind>=0;ind--){
dp[0]=max(dp[1]+prices[ind],dp[0]);
dp[1]=max(dp[0]-prices[ind],dp[1]);
}
return dp[1];
}
};
I think two array space optimisation is more readable and easier than 4 variable space optimisation..
Since curr[j] was only dependent on ahead[0] and ahead[1], we could further optimize this to a single array of size 2. In that way, we would have done this with just 2 variables. But for that inner loop will be from left to right i.e. 0 to 1 instead of 1 to 0 in normal space optimization and tabulation.
Learnt from prev video hn? Impressive ♥️
@@takeUforward All thanks to you! 😁♥️
Done and dusted in the DP revision :)
(1 min)
Nov'17, 2023 10:21 pm
understood
why we returned dp[0][1] in tabulation? by not dp[0][0]
Because 1 indicates you can purchase stock, you don't have any stock to sell, whereas 0 represents to sell the holded stock. Meaning with dp[0][0] meaning you are carrying the profit(i.e. answer) with some stocks yet to sell. Therefore returning dp[0][1]
I solved it using JUST 2 VARIABLES. Most space optimised simple solution.
Understood
int max_profit=0;
for(int i=1;i
Understood, sir. Thank you very much.
The below one seemed a reasonable approach to me when I first saw the question and had no idea about DP and all. And it works in o(n).
if (n == 0) return 0;
if(n == 2){
if (p[1] > p[0]) return p[1]-p[0];
else return 0;
}
long profit = 0;
for (int i = 0; i < n-1 ; i++){
int j = i;
while(j < n-1 && p[j+1] > p[j]){
j++;
}
profit += p[j]-p[i];
i = j;
}
return profit;
Understood. You explained really well!
i love you bro
if(n ==0) return 0;
long buy = values[0];
long res = 0;
for(int i =1;i values[i]) {
res += values[i-1] - buy;
buy = values[i];
}
}
return max(res,res + values[n-1]-buy);
most optimised
How can I create a data structure for buying and selling the stocks on my own?
greedy approach
if(prices.size()==0){return 0;}
int profit=0;
for(int i=0;iprices[i]){profit+=prices[i+1]-prices[i];}
}
return profit;
Understood!! very well explained!!!
mindBlowingggggggggggggggg
Understood clearly, thanks!
int maxProfit = 0;
for(int i=1;iprices[i-1]){
maxProfit+=prices[i]-prices[i-1];
}
}
return maxProfit;
this is better right?
so when we sell cant we buy on the same day again which eq takes care of that because after selling we are going to next index directly so we wont be able to buy on same day.
Nice one bro. Space optimization is lit
long profit=0;
for(int i=0;i
ur lectures are amazing sir
Understood!!! Amazing content!!!
Back to the previous days of dp on subsequences :)
Understood
Indeed understood!
NOTES ARE NOT THERE FOR THIS LECTURE??????? NOTES ARE NOT UPLOADED AFTER LECTURE 34
Understood bhaiya love this series😍😃
understood brother!! great explanation