# Best Time to Buy and Sell Stock with Transaction Fee

• This post is deleted!

• Very smart solution! Could you tell me how you came up with this solution? Is there any other resources or questions that can help me build up this knowledge/idea? Thanks.

• Can you explain your solution?Thanks!

• I feel this is semantically incorrect. `cash` has been updated before `hold = max(hold, cash - prices[i])`. But luckily if `cash` comes from the previous `cash`, it's fine. If `cash` is from `hold + prices[i] - fee`, then in `hold = max(hold, cash - prices[i])`, `cash - prices[i]` equals `hold + prices[i] - fee - prices[i]` which equals `hold - fee`, which is always smaller than `hold`, leading to a correct result. This is tricky and misleading. It would be better to use `preCash` and `preHold`.

• I think explaining optimal substructure and overlapping sub-problem would help vastly. its also unclear how formulas of cash and hold are arrived at

• @kenan3 LeetCode has several problems that are variations of this one. It should be obvious after you complete those:

• @benjamin19890721 I have completed buy and sell stock 1 and 2, and jump to this question. I found the way to solve this question is very different with those two questions, but it does look similar with buy and sell stock 3. I will figure it out. Thanks!

• This is awesome! Thank you for sharing.

• Question 1: if `you need to pay the transaction fee for each transaction`,
should this line of code

``````cash = max(cash, hold + prices[i] - fee)`
``````

be

``````cash = max(cash, hold + prices[i] - 2 * fee)`

``````

???

• Say one of the transactions are prices[j],prices[i],fee. Let's call them Pj, Pi.This means that the stock is purchased at Pj and sold at Pi with fee.
So for any Pi, first we find the best Pj. For that we need to find the best combination of "maximum until j" and Pj. So it becomes maxUntil-j + Pi - Pj - fee. Here maxUntil-j - Pj is called "hold". So it becomes hold + Pi - fee. So for any Pi we need to find the maximum "hold" and check out whether "hold + Pi - fee" > maxSoFar. I think I am able to explain. Indeed it's beautiful solution.

• Adding again: For any Pi we need to find the maximum (maxUntil-j + Pi - Pj - fee). Here Pi-fee is constant. So we need to find maximum maxUntil-j - Pj, i.e. maximum "hold". The following line does this.
hold = Math.max(hold, cash - prices[i]);

Then we see whether "hold + Pi - fee" > maxSoFar. Following line does this.
cash = Math.max(cash, hold + prices[i] - fee);

• Thanks for sharing, a remarkably elegant solution. I do understand the logic expressed, but can you give more insights regarding how one might come up with such a solution from scratch?

If I am holding a share after today, then either I am just continuing holding the share I had yesterday, or that I held no share yesterday, but bought in one share today: `hold = max(hold, cash - prices[i])`
If I am not holding a share after today, then either I did not hold a share yesterday, or that I held a share yesterday but I decided to sell it out today: `cash = max(cash, hold + prices[i] - fee)`.
Make sure `fee` is only incurred once.

• @vegito2002 Actually more you practice same kind of solution, more insight you develop. Say for example, rather than seeing the solution you may spend 1/2 days after it. You spend small stretches and do brain storming. Automatically you will find new perspectives. I believe that this is the only way, giving time to a problem...

• @vegito2002 Actually more you practice same kind of solution, more insight you develop. Say for example, rather than seeing the solution you may spend 1/2 days after it. You spend small stretches and do brain storming. Automatically you will find new perspectives. I believe that this is the only way, giving time to a problem...

This is what I think... completely my view... others definitely may have their views as well..

• Why is fee considered only once? Should
'''
hold = Math.max(hold, cash - prices[i])
'''
also have a fee?

• pretty cool solution :)

If I am holding a share after today, then either I am just continuing holding the share I had yesterday, or that I held no share yesterday, but bought in one share today: `hold = max(hold, cash - prices[i])`
If I am not holding a share after today, then either I did not hold a share yesterday, or that I held a share yesterday but I decided to sell it out today: `cash = max(cash, hold + prices[i] - fee)`.
Make sure `fee` is only incurred once.