Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming
Vložit
- čas přidán 28. 07. 2024
- / tusharroy25
github.com/mission-peace/inte...
github.com/mission-peace/inte...
github.com/mission-peace/inte...
Given an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions. Transactions cannot occur in parallel. One transaction should complete before starting another transaction.
Don't miss the optimization at 13:23.
It reduces the time complexity from O(k*d*d) to O(k*d)
k = max transactions, d = total days
Thanks. I would still start with the first solution in an interview and then optimize
@@abhishekkumar-ui7xm yupp
Thanks this saved me some time! 😅
Cannot thank you enough for the tutorial! I've seen the formula in other blogs but got quite confused by the idea behind it, you just saved me tons of time!
Great video Tushar. You solved an all time mystery so simply. Brilliant!!! Thanks
this is the clearest explanation I've seen on the internet
thanks
Well done Tushar .. :)
Hats Off for your clarity in the explainations (y)
Nice work, Tushar! Thank you for explaining in such a clear way
First attempt:
Me: "What!?"
Second attempt:
Me: "Aha, that how we calculating T[ i ] [ j ] "
Third attempt:
Me: "What!? No, I should take a walk"
Fourth attempt (after the walk):
Me: "Mother of fucking god. So we just looking for the difference between previous day profit and previous day price to find if it's the max, and if it is we are adding it to the price on an actual day! And if it's larger than previous day than it's a max profit!"
3 hr 20 min. I'm fucking happy...
Damn Vitalii
Just reached the point where your final Conclusion made sense.
Thanks, BTW, for the Motivation :P
Your Fourth attempt makes most sense. So basically if I need to find an M from 0..j-1 and I already know the best M from 0..j-2 then just compare previous M with the new j-1 index. This is similar to what you would do if you need to store some prefix max for an array.
Tushar, you're explanation is pretty neat and simple to understand. Thanks for explaining these problems simpler and easy to understand.
You have the biggest playlist on hard DPs, worked damn hard man
Such a genius explanation. I looked many other videos and people skipped the most important thing which is the thought process. Thanks! I am a fan now.
I've been trying to solve this problem for a long time! Almost everything on the internet was complex and confusing. Your approach is best solution available on the internet!
Hey Tushar! Thank you so much! Your videos are of great help! Keep it coming! :)
Thank you for the great explanation and especially the step by step process of moving from a logical initial algorithm to an even faster one. One thing I wanted to mention is specifically about the implementation of the code. Maxdiff should be updated prior to determining the max value of T[i][j] because we need to know if the previous maxDiff is larger or the new difference that was introduced.
Brilliant! Thank you ! Not until I watched this video did I realize the solution!
Very helpful, thank you for your work!
Can not be btter! Thank you so much! Tushar Roy.
The formula is right. Just make it clear:
Formula is
maxDiff = max(maxDiff, T[i-1][j-1] - prices[j-1])
T[i][j] = max(T[i][j-1], prices[j] + maxDiff)
or
T[i][j] = max(T[i][j-1], prices[j] + maxDiff)
maxDiff = max(maxDiff, T[i-1][j] - prices[j]) // used for next turn
1
Thanks for the effort in preparing this video. It was an almost perfect explanation.
Frankly, I was working on this problem on leetcode and was not able to understand the solutions can be found online. But your explanation is so clear and well organized. I dunno remember how many your videos I've watched and they always help. I feel I must say thank you to you!
Thanks a lot for this! I just could not understand the final optimization step before watching this video, which reduces the time complexity from O(k*n^2) to O(k*n), probably because I kept trying to understand the "best" solution without trying to understand the slightly worse solutions.
I believe there is a way to reduce the space complexity to O(n) as well, by making two arrays called prev and next, each of size n=prices.size(), and calculating the maxDiff from prev while filling the solution to the DP in next.
We can further reduce the space to just one n-sized array, named T, by keeping two variables named maxDiff and newMaxDiff, and calculating newMaxDiff=max(maxDiff, T[j] - prices[j]), then using maxDiff to calculate T[j], and then setting maxDiff = newMaxDiff for the next iteration to use.
Another thing I realized is that if K is greater than or equal to N/2, then the array stops changing between iterations. So we can completely skip this algorithm and use the standard *maximize profit with any number of transactions* solution.
Very Helpful! Good job explaining the algo.
Amazing explanation! Finally understood why this works :)
I just never got this question but now i have just because of you
lol
Good job, I never got it before but your explanation is clear!
I believe a better formula is the following:
T[i][j] = max{ T[i][j-1] , prices[j]-prices[m]+T[i][m-1] } m goes from 0 to j-1.
Please notice that I use m-1 instead of m in the video. Because T[i][j] represents the maximal profit that one can get at the end of the day j, inclusive. That said in the formula of the video, where the last term is T[i][m], it could be count twice. However, T[i][j] may have hidden the issue in the algorithm so that it won't show up.
My two cents, the above formula makes it clearer.
Anyway, great tutorial. Always love watching this guy's video, :)
i think either m or m - 1 is ok, whether we allow sell and buy at the same day has no effect on max profit.
1) if we have up-rising price array, we will always return max profit by buying at 1st day and sell at last day
2) if we have down-falling price array, we will have a natural gap that makes the condition become "we won't sell and buy at the same day", which is that we maintain the old max profit and wait for the next up-rising period to buy.
two things combined, using m can represent m - 1 so we don't have to worry about "counting twice". (and also m is easier to write since u don't need to deal with boundary case where m - 1 could be -1)
The video is nice. I think it would be great if you can also discuss about the Best Time to Buy and Sell Stock with Cooldown. Thanks a lot!
Very Helpful Tushar Sir .. :-)
thanks a lot Tushar
you made a complicated problem, easy and simple to grab
It's helpful. Good diction. Thanks for the video.
You got a new subscribe here. Great work!
really helpful , keep it simple and effective
Thanks for your efforts. Great explanation.
Sir, your videos are a gem. I am pretty sure I will come back in 2026 to watch this again.
You actually explain how to derive maxDiff from the recurrence relation formula, you're such a champ Tushar!
Thanks. your explanation is very nice
yes bro,but unfortunately he has not uploaded his lectures since 6 month.
Extremely clear! Thank you so much
Thanks dear .Now I am able to understand the logic behind the problem.Brilliant,Awesome work...
What is the logic behind calculating the MaxDiff ?
thanks for explaining it so elegantly.
Really helpful video with such a detailed explanation !
I finally understood all the leetcode solution by watching your video. Concept is clear now. Thanks.
What if i want first to sell and then buy for k transactions? i dont initialize the first column with zeros?
In 25:05 it must have been like maxdiff = max(maxdiff, T[i-1][j-1]-price[j-1]) , explanation is awesome👏👍
Thanks for the awesome explanation, one thing variables inside a for loop need not be named i, j, k always they can be named as day, transaction etc. too
Hi. Thanks for your great video. In your 2nd part of the equation, when you are looking for the best transaction {m-->i}, why do you use T[i-1][m] instead of T[i-1][m-1]. The thing is If you found that m is the best day on which to buy stock for transaction (i), then you can't include that day in T[i-1][m] since you are not allowed to use the same day to both sell stock for the (i-1)th transaction and buy stock for the (i)th transaction.
I would appreciate if you correct my understanding if needed :-)
He used it after the computing the transaction so this step is used in next transaction computation actually.
Bro. I had the same confusion but later on I realize that we were wrong. price[j] - price[m] is the earning of buy at m and sell at j. T[i-1][m] is to sell at m. If we add T[i-1][m] + price[j] - price[m], it means we do nothing at m! It cancels out to buy and sell together.
@@shuaizhao5622 Yes that is tricky part. Prior to watch that video i was stuck throughout a day after assuming T[i-1][m-1] + price[j] - price[m] :(
@@shuaizhao5622 T[i-1][m] may or may not include selling at mth day. However if it does include selling at mth day then the question arises are we allowed to first sell and then buy at the same day?
I had the same question. It seems his solution is allowing for buying and selling on the same day, which I don't believe the leetcode question allows.
thank you for this video!
Thank you very much. Your explanation was better than other videos.
How to come up with such an algorithm in a 45 mins interview setting. There is no explanation on how to arrive at this solution.
In 45 minutes you have to introduce yourself, have a small talk, solve the problem and then answer for additional questions. To solve a problem you have to 1) Come up with an algorithm; 2) Write code; 3) Check your code. So, I'd say you have 10-15 minutes at most to come up with an algorithm :)
czcams.com/video/Pw6lrYANjz4/video.html . This should help you on the intuition behind the formula.
I like dynamic programming but I want to understand on how we arrive to a solution/formula like this...
@@ambikabasappachandrappa9409 think about it this way. One any given day, you either do a transaction or you don't. and your goal is to maximize the profit between these two options. Let's define a 2-D array for maximum profit of doing i interactions up until day j. T[i,j]
if you don't do a transaction, your best profit will be the profit you acquired up until day j-1 ( T[i,j-1] ). and if you do a transaction, your profit will be the best combination of your past transactions (T[i-1,m]) and your current transaction (price[j] - price[m]) for each of the m days prior to this one. so between these two options (doing a transaction or not doing it) you need to find the maximum profit. hence you reach the formula on the board:
T[i,j] = max ( T[i,j-1], max over m (T[i-1,m]+price[j]-price[m])
this way of reasoning about the solution is predominant in dynamic programming. Many of such problems can be solved using a similar logic (e.g. the Knapsack problem)
@@surajch2678 Thanks
Thank you so much. Its very helpful.
Thanks buddy. great help. :)
Great explanation. Just wondering in printActualSolution() method why did you define 'Deque stack = new LinkedList();' , why not simple stack something like 'Stack st = new Stack();'?
I wrote the memoized recursive function for this but couldn't come up with the bottom up solution. Can someone tell me what is the time complexity for memoized version?
Only one word : "Awesome",
Do you have trie related interview question's videos?
+Tushar Roy Ok, any planning to make in near future.?
Not much as I have not tried yet more problems. Still I would like to ask one question.
I am talking about efficient implementation in java, what is best way to implement trieNode when we are dealing with alphabets then HashMap is good idea or array of 26 size is good idea? I think both are same. what your thoughts on this?
OK thanks.
Why is it not this: T[i][j] = price[j]-price[m] + T[i-1][m-1]
instead of this: T[i][j] = price[j]-price[m] + T[i-1][m]
As if T[i-1][m] contains the case that we are selling the stock on mth day, then we cannot buy the stock on mth day. Pls explain
It actually doesn't matter. If you sell a stock on some day and buy the stock on that same it's as if you didn't do any transaction. So for example at 8:36 , he assumes that we bought 2 on day 0, sold it on day 1 at 5, then bought 5 again at day 1 and sold it at 7 on day 2. It's as good as we never did anything on day 2 and directly sold the stock priced 2 at a price 7.
That true and its correct explanation as we can not buy and sell on same day. Above solution works and makes code concise but during interview any followup question would be hard to explain and prove, if we use T[i][j] = price[j]-price[m] + T[i-1][m]. so we can use if (m==0) then T[i][j] = price[j]-price[m] else T[i][j] = price[j]-price[m] + T[i-1][m-1]. Then move to optimized solution.
@@patelmiki Willl this really work bro?
check at 9:50
best dynamic programming tutorial ever!
crystal explanation. Well Done!
thank you very much, great video
Thanks for the explanation and that cool optimization trick
Such a genius!
What if we have two stocks, is there any algorithms to solve the problem please?
Good work man 👏👏👏
Best explanation of this algorithm. Thank you.
so we can get optimized solution only after figuring out the O(k*n*n) solution? or by practice one can directly get the second solution?
Hi Roy,
Thanks for you video!
But I have some confusion with this problem. Could you please help to explain it a bit?
In my solution, the relation is:
profit[t][i] = max(profit[t][i-1], max(price[i] - price[j] + profit[t-1][j]))
for all j in range [0, i-1] and price[i]>price[j](please note to this).
In my test the above relation works as fine as the solution posted in this article so I think both relations are good. But my solution is not clean and prevent me from optimizing it to O(kn).. So could anyone explain to me why we don't need consider the comparison price[i]>price[j]? Only when price[j]
Thanks a lot !
Thanks! Much better than the highest rated leetcode comment
Thanks for the great video. Just one question. Is this solution is based on the assumption that we might sell and buy on the same day? I'm asking this because we are adding [k-1][m] and not [k-1][m-1].
same doubt can u explain
you can sell and buy on the same day but you don't have to.
Shouldn't it be T[i-1][m-1], instead of T[i-1][m] ?
At day m, the max profit you can get is, say x. This x includes Do and Don't do transaction on day m. Even if you do the transaction on day m (say you sell, and make a profit on day m), you can still buy again on day m, and make a profit at day > m. So T[i-1][m] is correct.
R we allowed to sell and buy on same day? i think no pls rectify
Hi.. great job man..!! Your videos are always a treat to watch.
Just one query though - we should only be allowed to either buy or sell on a day right but your explanation seems to be considering that one could sell and then buy on the same day (Mth day) marking the beginning of another txn. I don't think that's possible or is it? Kindly correct me if wrong
Yes I've seen this problem presented as being unable to buy and sell on the same day.
I thought we cannot buy on the same day we sell. But according to the video, it seems like we can do it. But suppose there is a cool down time 'c', then the formula is price[j] - price[m + T[i-1][m-c] where m >= c
pretty cool .. computers are dumb .. but tushar is smart .. great job .
How do you come up with the 2d array parameters on the first whiteboard? T[transaction][day]
It's great post. I have a query about print solution did not follow the intuition behind how print solution working as it's working..
i came up with the code for infinte transaction ,thnx to ur video sir i came to know what the problem really was and ur solution saved my lazy ass
Always the best
Can this be done recursively ? I know its not efficient. But I usually do these recursively and then convert the solution to DP. That way its more understandable. Every DP problem has a recursive sol and DP sol follows from recursive one.
yup it can be done
Great video Tushar with two solutions...Is der any other problem which ll have same solution procedure...Like LIS and maximum sum increasing subsequence..
Man you are awesome
Great video tushar.
Just on a lighter note, was wondering about the ascent , it feels manipulated.
great explanation
Amazing solution !!!!
could you reexplain what exactly the "max diff" stands for in this case?
While back tracking you said 10 is the total profit and 3 is the profit you made on 7th day,
3 is the price on 7th day not the profit.
Now at 7th day we have a profit of 10 and the 10 is not coming from previous cell, which mean we did SELL on 7th day.
And now previous cell is saying profit = 8 and the mean 7th day contributed in profit = 10-8 = 2, now the price is 3 at 7th day and in order to have profit of 2 we should have bought at 3-2=1 which is 6th.
Same applied to day 4.
I am preparing for interviews and i find your videos really helpful.
Just one suggestion or correction regarding this video for the maxDiff formula :
For k =3, when you are calculating the maxDiff :
On board formula is written as : maxDiff = max(maxDiff, T[i-1][j] - price[j] )
In video you explained with : maxDiff = max(maxDiff, T[i-1][j-1] - price[j-1] ) ( Time of video portion 19 mins to 22 mins)
I checked with Board formula , i am getting the same answer and your code is proof of correctness of board formula.
Could you please check once or am i missing something?
Using j instead of j-1 is also correct because it just means buy on the jth day and immediately sell it on the jth day. so the adding profit is actually 0, which makes no difference.
Yes correct.
When you are selling at T[i] for 2nd transaction, and you assume the stock was bought between T[0] to T[i-1]. Agreed.
Out of T[0] to T[i-1], let's say you bought at T[i-2]. Then your previous/1st transaction should end before T[i-2]. Not till T[i-2].
Isn't?
It's awesome !
hi could you also upload a video on buy and sell any number of times. thanks!
+Tushar Roy I think your solution for this question only gives the maximum profit which she can earn but not the details of buying and selling day. If i am wrong then please correct me.
Thanks. I understand after listening to your explanation. only you....123 is to difficult to me
is there any video tutorial for AVL tree node deletion ?
+Tushar Roy ok thank you
why is it not price[j] - price[m] + T[i-1][m-1]...since m is already included in the new transaction group, we are left with only 0 to m-1 days with one transaction less....so I suppose it should be T[i-1][m-1] and not T[i-1][m]. Someone pls explain...
Yeah I have the same doubt, did you get it now? If yes, then pls explain
@Tushar Pls solve this
@@rashmikiranpandit8962 not yet.. :(
@@rashmikiranpandit8962 hey...i got it now...this is because we can sell and purchase again on that same mth day..
Last row is coming wrong as per the first formula . Is that first formula only for n-1 rows ...
Great video
veryyyyyy impressive solution !!!!!
what about this formula,
min=0;
Loop
T[i][j]= Max{ T[ i-1] [ j ], P[ j ] - p [ min ] }
if( p[ j ] < p [ min ] ) min=j;
Thank you!
shouldnt the maxdiff = max(maxDiff ,T[i-1][j-1]-pricce[j-1])
That is correct. T[i][j] = max(T[i][j-1], P[j] + max(maxDiff, T[i-1][j-1] - P[j-1]);
For a transaction k, initial maxDiff = T[k-1][0]
Just didn't understand why max profit is //max(profitprevious with no transaction, (price[i] - price[m] + profit[i])) .
why not we are adding profit[i-1] like T[i-1[j-1]] why T[i-1][j] , m moves from m=0...i-1 not i ?
you are the best
if t[i][j] is doing max i transactions upto jth day then shouldn't it be
t[i][j]=price[j]-price[m]+t[i-1][*m-1*] instead of
price[j]-price[m]+t[i-1][*m*]
为啥花花酱没有这题的讲解？