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
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.
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 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)
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.
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.
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
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?
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.
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 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!
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)
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.
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!
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.
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
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.
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();'?
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?
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
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 ?
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
Great video Tushar with two solutions...Is der any other problem which ll have same solution procedure...Like LIS and maximum sum increasing subsequence..
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.
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]
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...
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*]
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.
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?
Tushar , an improvement tip , we always memoize or store a recursive step , so if you also show a recursive solution first and then teach us how you are storing that it would be a great help and improve the quality of your tutorials .
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?
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
i have been in trade with Pat Brown for the past Eight months now, since the firm of the last broker i was working with ran into bankruptcy. i always receive my weekly profit payment
You guys seriously think the best way to advertise pat brown is to leave it as a comment under a video with the words 'profit' and 'stock'? how common is it that you have 7 likes and also 6comments + your own post. All comments made before 8 months and no comments after that. Very strategic way of advertising.
