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...
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.
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
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.
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!
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!
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.
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 :-)
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 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 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)
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.
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 :)
@@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)
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
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.
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.
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].
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.
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.
You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). i guess that T[i-1][m] should be T[i-1][m-1] right??? Correct me if I'm wrong
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?
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();'?
at 17:00. TR: i don't know if you understand that or not me: hahahaha; yes, but after replaying the section [14:00 - 17:00] about 3 times over. jokes apart, great explanation. kudos!
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]
I have difficulty to understand the way other guys resolve this problem by using DP solution. It is much easy to understand it by your explanation. You really help me out! Thanks!
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...
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
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 ?
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.
Great video Tushar with two solutions...Is der any other problem which ll have same solution procedure...Like LIS and maximum sum increasing subsequence..
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
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?
Leetcode set a trap in here. If the number of maximum transactions k is much greater than the number of days, the dp algorithm for large k is not necessary and Leetcode TLE on this algorithm. Instead just use the method from Best Time to Buy and Sell Stock II when k is large. Check the adapted C++ solution in earlier comment.
at T[2][1], how is it possible you could have transacted 2 times by the 2nd day? buy on day 1 and sold one day 2, you've completed 1, not 2 transactions
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*]
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?
![Burst Balloon Dynamic Programming[Leetcode]](http://i.ytimg.com/vi/IFNibRVgFBo/mqdefault.jpg)
![Burst Balloon Dynamic Programming[Leetcode]](/img/tr.png)
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! 😅
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.
this is the clearest explanation I've seen on the internet
thanks
You have the biggest playlist on hard DPs, worked damn hard man
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
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 finally understood all the leetcode solution by watching your video. Concept is clear now. Thanks.
Tushar, you're explanation is pretty neat and simple to understand. Thanks for explaining these problems simpler and easy to understand.
In 25:05 it must have been like maxdiff = max(maxdiff, T[i-1][j-1]-price[j-1]) , explanation is awesome👏👍
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!
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!
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!
You actually explain how to derive maxDiff from the recurrence relation formula, you're such a champ Tushar!
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.
Sir, your videos are a gem. I am pretty sure I will come back in 2026 to watch this again.
Amazing explanation! Finally understood why this works :)
Thank you very much. Your explanation was better than other videos.
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.
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)
Great video Tushar. You solved an all time mystery so simply. Brilliant!!! Thanks
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.
Best explanation of this algorithm. Thank you.
I just never got this question but now i have just because of you
lol
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 :)
ua-cam.com/video/Pw6lrYANjz4/v-deo.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
Thanks dear .Now I am able to understand the logic behind the problem.Brilliant,Awesome work...
best dynamic programming tutorial ever!
Nice work, Tushar! Thank you for explaining in such a clear way
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.
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
Well done Tushar .. :)
Hats Off for your clarity in the explainations (y)
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
Brilliant! Thank you ! Not until I watched this video did I realize the solution!
Thanks for the explanation and that cool optimization trick
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.
Thanks! Much better than the highest rated leetcode comment
Good work man 👏👏👏
Hey Tushar! Thank you so much! Your videos are of great help! Keep it coming! :)
Hats Off, the amount of effort you've put into really deserves an applaud, the clearest explanation I've seen, you make it understandable, sublime!
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!
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
thanks a lot Tushar
you made a complicated problem, easy and simple to grab
Extremely clear! Thank you so much
crystal explanation. Well Done!
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.
sir at 20:15 the maxDiff Value is 5 insted of 4
Thanks for the effort in preparing this video. It was an almost perfect explanation.
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.
Really helpful video with such a detailed explanation !
You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
i guess that T[i-1][m] should be T[i-1][m-1] right???
Correct me if I'm wrong
pretty cool .. computers are dumb .. but tushar is smart .. great job .
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.
veryyyyyy impressive solution !!!!!
What is the logic behind calculating the MaxDiff ?
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();'?
at 17:00.
TR: i don't know if you understand that or not
me: hahahaha; yes, but after replaying the section [14:00 - 17:00] about 3 times over.
jokes apart, great explanation. kudos!
Good job, I never got it before but your explanation is clear!
You got a new subscribe here. Great work!
I think there is mistake in the optimised formulae for maxDiff it should be max(maxDiff,T[i-1][j-1]-price[j-1])
correct
thanks for explaining it so elegantly.
How do you come up with the 2d array parameters on the first whiteboard? T[transaction][day]
Very Helpful! Good job explaining the algo.
What if i want first to sell and then buy for k transactions? i dont initialize the first column with zeros?
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]
I have difficulty to understand the way other guys resolve this problem by using DP solution. It is much easy to understand it by your explanation. You really help me out! Thanks!
could you reexplain what exactly the "max diff" stands for in this case?
Very Helpful Tushar Sir .. :-)
Last row is coming wrong as per the first formula . Is that first formula only for n-1 rows ...
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..
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]
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
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?
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 ?
really helpful , keep it simple and effective
Great video tushar.
Just on a lighter note, was wondering about the ascent , it feels manipulated.
It's helpful. Good diction. Thanks for the video.
Amazing solution !!!!
great video
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..
为啥花花酱没有这题的讲解？
You saved me. You are god to me.
OK....here, a buy and a sell together are counted as a transaction right?
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..
you are the best
hello ,although your optimised code is running but your explanation and code doesn't match ,i think it should be like this for(j=1;j
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
The reason of T[i-1][m] and not T[i-1][m-1] is beacause you can do buy sell or sell buy on same day but not buy buy or selll seell
ok
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?
11:20 lmao that voice crack ruined my attention span
***** not your fault man haha don't worry. Video was still very helpful
Thanks for your efforts. Great explanation.
Shouldn't maxDiff = max(maxDiff, T[i-1][j-1]-price[j-1]) based on your video?
yeah it should be the same as u said
His code calculates max diff before incrementing j by 1. And yours is right if its after, so both are fine with the context when it is done.
Man you are awesome
Thanks. your explanation is very nice
yes bro,but unfortunately he has not uploaded his lectures since 6 month.
His solution is very nice, but when I implement that in Leetcode, It pass almost test cases, but last one show Memory Limit Exceeded
same here ... do you know why yet ?
Leetcode set a trap in here. If the number of maximum transactions k is much greater than the number of days, the dp algorithm for large k is not necessary and Leetcode TLE on this algorithm. Instead just use the method from Best Time to Buy and Sell Stock II when k is large. Check the adapted C++ solution in earlier comment.
@@jieyan8143 hey, thanks. It helped.
at T[2][1], how is it possible you could have transacted 2 times by the 2nd day? buy on day 1 and sold one day 2, you've completed 1, not 2 transactions
to answer my own question: T[i][j] is defined as max profit on day (j+1) with at most (i+1) transactions, so that makes sense
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*]
Thanks buddy. great help. :)
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?
thank you very much, great video
thank you for this video!