Best Time to Buy and Sell Stock with Transaction Fee


I feel this is semantically incorrect.
cash
has been updated beforehold = max(hold, cash  prices[i])
. But luckily ifcash
comes from the previouscash
, it's fine. Ifcash
is fromhold + prices[i]  fee
, then inhold = max(hold, cash  prices[i])
,cash  prices[i]
equalshold + prices[i]  fee  prices[i]
which equalshold  fee
, which is always smaller thanhold
, leading to a correct result. This is tricky and misleading. It would be better to usepreCash
andpreHold
.

@kenan3 LeetCode has several problems that are variations of this one. It should be obvious after you complete those:
 https://leetcode.com/problems/besttimetobuyandsellstock/description/
 https://leetcode.com/problems/besttimetobuyandsellstockii/description/
 https://leetcode.com/problems/besttimetobuyandsellstockiii/description/
 https://leetcode.com/problems/besttimetobuyandsellstockiv/description/

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

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 maxUntilj + Pi  Pj  fee. Here maxUntilj  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 (maxUntilj + Pi  Pj  fee). Here Pifee is constant. So we need to find maximum maxUntilj  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);

For future readers:
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 surefee
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...

@sankar4leetcode said in Best Time to Buy and Sell Stock with Transaction Fee:
@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..

@vegito2002 said in Best Time to Buy and Sell Stock with Transaction Fee:
For future readers:
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 surefee
is only incurred once.Good explanation!
It's easier to understand!
Thanks!