Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming

[@ShikharPrasoon]

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

[@speedmishra13]

Thanks. I would still start with the first solution in an interview and then optimize

[@ShivamKumar-qv6em]

@@abhishekkumar-ui7xm yupp

[@sahilanower9189]

Thanks this saved me some time! 😅

[@brucezu574]

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

[@lakshaygarg101]

1

[@NizGravit]

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...

[@astroash]

Damn Vitalii

[@sulaimant5690]

Just reached the point where your final Conclusion made sense. Thanks, BTW, for the Motivation :P

[@salilkansal4988]

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.

[@effy1219]

this is the clearest explanation I've seen on the internet thanks

[@biboswanroy6699]

You have the biggest playlist on hard DPs, worked damn hard man

[@azn0180]

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.

[@venkatakrishnansowrirajan573]

Tushar, you're explanation is pretty neat and simple to understand. Thanks for explaining these problems simpler and easy to understand.

[@varshath2]

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!

[@shuaishao621]

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!

[@subashthapa5475]

I finally understood all the leetcode solution by watching your video. Concept is clear now. Thanks.

[@cristianouzumaki2455]

Sir, your videos are a gem. I am pretty sure I will come back in 2026 to watch this again.

[@swethamuthuvel6526]

In 25:05 it must have been like maxdiff = max(maxdiff, T[i-1][j-1]-price[j-1]) , explanation is awesome👏👍

[@huali327]

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!

[@jiayincao254]

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, :)

[@taowang9735]

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)

[@ThePaullam328]

You actually explain how to derive maxDiff from the recurrence relation formula, you're such a champ Tushar!

[@StarPlatinum3000]

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.

[@sherryfan161]

Amazing explanation! Finally understood why this works :)

[@xgreenbeansoupx]

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.

[@freezefrancis]

Well done Tushar .. :) Hats Off for your clarity in the explainations (y)

[@charvakpatel962]

I just never got this question but now i have just because of you

[@Vendettaaaa666]

lol

[@sohamchakravarty472]

Great video Tushar. You solved an all time mystery so simply. Brilliant!!! Thanks

[@chetanshrivastava3762]

Thanks dear .Now I am able to understand the logic behind the problem.Brilliant,Awesome work...

[@kevinshindler7014]

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!

[@kaichenghu3826]

Nice work, Tushar! Thank you for explaining in such a clear way

[@jdragon8184]

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

[@raihanulalamhridoy4714]

Thank you very much. Your explanation was better than other videos.

[@kobebyrant9483]

best dynamic programming tutorial ever!

[@sanchayshrivas7749]

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!

[@speedmishra13]

Thanks! Much better than the highest rated leetcode comment

[@gauravbuche7211]

Hey Tushar! Thank you so much! Your videos are of great help! Keep it coming! :)

[@KemoLeno]

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 :-)

[@prakhargandhi8919]

He used it after the computing the transaction so this step is used in next transaction computation actually.

[@shuaizhao5622]

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.

[@varungoyal2975]

@@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] :(

[@saurabhakumarnayak5879]

@@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?

[@electric336]

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.

[@益达-k6q]

Brilliant! Thank you ! Not until I watched this video did I realize the solution!

[@yanivgardi9028]

thanks a lot Tushar you made a complicated problem, easy and simple to grab

[@jamesfaust1485]

the stock market has been of immense success. i make $500 profit weekly from my stock investment with my expert analyst and asset manager Pat Brown

[@climbaron3798]

am glad u know Pat Brown. He has also helped me earn a fortune from stock trading.

[@lawsondarlington6064]

i really appreciate the fact that Pat Brown puts his best in investors trade and he doesn’t have issues with profit payments

[@jasoncole9369]

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

[@sambliz276]

this is all amazing. am saving up to get into trade with Pat Brown in the forthcoming weeks. someone should give me his contact please.

[@sandeepvedavyas8701]

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.

[@momkid90]

Best explanation of this algorithm. Thank you.

[@rakesh0054]

Thanks for the effort in preparing this video. It was an almost perfect explanation.

[@evelynross1043]

pretty cool .. computers are dumb .. but tushar is smart .. great job .

[@lijiechen2119]

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!

[@shoryagoswami3463]

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

[@bird6472]

Yes I've seen this problem presented as being unable to buy and sell on the same day.

[@akashjain35]

Really helpful video with such a detailed explanation !

[@rashmikiranpandit8962]

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

[@vrukshanikam6743]

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.

[@patelmiki]

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.

[@lakshyaagarwal2005]

@@patelmiki Willl this really work bro? check at 9:50

[@gxbambu]

Good job, I never got it before but your explanation is clear!

[@TM-qc5oz]

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.

[@romanpanchenko9009]

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 :)

[@surajch2678]

kzbin.info/www/bejne/hqiZnaWPdrOdsJY . This should help you on the intuition behind the formula.

[@ambikabasappachandrappa9409]

I like dynamic programming but I want to understand on how we arrive to a solution/formula like this...

[@marjansherafati6913]

@@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)

[@ankit5373]

@@surajch2678 Thanks

[@atharvakulkarni3007]

Thanks for the explanation and that cool optimization trick

[@HAAH999]

You got a new subscribe here. Great work!

[@aniruddhadesai4722]

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!

[@Mankind5490]

11:20 lmao that voice crack ruined my attention span

[@Mankind5490]

***** not your fault man haha don't worry. Video was still very helpful

[@ivyxue6443]

Extremely clear! Thank you so much

[@akashmehra3111]

Very Helpful! Good job explaining the algo.

[@PranayKumarAggarwal]

Very Helpful Tushar Sir .. :-)

[@jaden2582]

crystal explanation. Well Done!

[@sriramphysics5853]

Good work man 👏👏👏

[@jpcsr8887]

It's helpful. Good diction. Thanks for the video.

[@anuragmanchanda]

Thanks for video :) Another small update(ruby code) t = Array.new(k+1){Array.new(prices.length, 0)} i = 1 while(i

[@manishsat]

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.

[@tapeshmittal3287]

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].

[@tushargoyaliit]

same doubt can u explain

[@SaurabhPatel]

Only one word : "Awesome", Do you have trie related interview question's videos?

[@SaurabhPatel]

+Tushar Roy Ok, any planning to make in near future.?

[@SaurabhPatel]

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?

[@SaurabhPatel]

OK thanks.

[@durgeshchoudhary]

thanks for explaining it so elegantly.

[@kylemorgan1933]

Shouldn't it be T[i-1][m-1], instead of T[i-1][m] ?

[@terrychen7673]

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.

[@shobhitchaturvediindia]

really helpful , keep it simple and effective

[@ShubhamMahawar_Dancer_Actor]

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

[@xiaoqinglin6112]

Geat video. You look like the guy in three idiots, the smartest one~

[@mebinjacob_UF]

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

[@audiobeginner]

You saved me. You are god to me.

[@puneetgarg6069]

Thanks. your explanation is very nice

[@Aryan-wv6qe]

yes bro,but unfortunately he has not uploaded his lectures since 6 month.

[@yuexian7981]

veryyyyyy impressive solution !!!!!

[@parveenchhikara6961]

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?

[@yingqian2034]

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.

[@shatendrasingh6273]

Yes correct.

[@vivekpal1004]

Thanks for your efforts. Great explanation.

[@shamanthnorway]

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

[@kuntalgorai9744]

I think there is mistake in the optimised formulae for maxDiff it should be max(maxDiff,T[i-1][j-1]-price[j-1])

[@TheCodeThoughts]

correct

[@pramodnandy2095]

Great video Tushar with two solutions...Is der any other problem which ll have same solution procedure...Like LIS and maximum sum increasing subsequence..

[@akashshukla3163]

Great video tushar. Just on a lighter note, was wondering about the ascent , it feels manipulated.

[@atharvakulkarni3007]

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

[@arpan8107]

you are the best

[@priyamchandra1901]

Amazing solution !!!!

[@MrSachintelalwar]

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();'?

[@josephwong2832]

great video

[@ericchen6759]

Such a genius!

[@vishwanathgaur2511]

Thanks buddy. great help. :)

[@harsha281292]

Thank you so much. Its very helpful.

[@sundeep1501]

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?

[@fghjklijk789]

I was just trying to solve this puzzle from geeksforgeeks and your video made it even more simpler...Thanks

[@abhishekkumargupta3043]

Well, it gives memory limit exceeded in Leetcode for cases where no. of transactions are equal to or greater than no. of days. Just use the logic for using as many transactions as possible (best-time-to-buy-and-sell-stock-ii). Here's my C++ solution: leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/811258/C%2B%2B-Fastest-Simplest-Solution-or-DP-or-O(k*d)

[@gamma48]

thank you very much, great video

[@nguyenhoanvule5755]

His solution is very nice, but when I implement that in Leetcode, It pass almost test cases, but last one show Memory Limit Exceeded

[@raghuveernaraharisetti]

same here ... do you know why yet ?

[@jieyan8143]

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.

[@abhishekkumargupta3043]

@@jieyan8143 hey, thanks. It helped.

[@vaibhavsharma1653]

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

[@tushargoyaliit]

ok

[@shishirmohire9789]

Always the best

[@李根-s3z]

thank you for this video!

[@atuljoshi9187]

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 ?

[@pranavgaur6399]

Man you are awesome

[@budsyremo]

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 .

[@astitvasrivastav9484]

If you are in comment section to resolve the last testcase of leetcode , just go back and for prices.size()

[@kuralamuthankathirvelan]

What is the logic behind calculating the MaxDiff ?

[@ayushjindal4981]

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...

[@rashmikiranpandit8962]

Yeah I have the same doubt, did you get it now? If yes, then pls explain @Tushar Pls solve this

[@ayushjindal4981]

@@rashmikiranpandit8962 not yet.. :(

[@ayushjindal4981]

@@rashmikiranpandit8962 hey...i got it now...this is because we can sell and purchase again on that same mth day..

[@yuzhichu1779]

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]

[@neerajchoudhary3709]

tushar roy is vintage.

[@akhilendrasingh7992]

great explanation

[@rajcodingworld7768]

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..

[@jingweiguan4556]

Thanks. I understand after listening to your explanation. only you....123 is to difficult to me

[@swamysriman7147]

OK....here, a buy and a sell together are counted as a transaction right?