Best Time to Buy and Sell Stock with Transaction Fee


  • 1

    Click here to see the full article post


  • 0
    Q
    This post is deleted!

  • 0
    K

    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.


  • -1
    J

    Can you explain your solution?Thanks!


  • 2
    I

    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.


  • 0
    S

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


  • 1

  • 0
    K

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


  • -1
    V

    Could u tell clearly about your solution ?


  • 0
    L

    This is awesome! Thank you for sharing.


  • 0
    U

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

    ???


  • 0
    S

    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.


  • 0
    S

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


  • 0

    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?


  • 0

    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 sure fee is only incurred once.


  • 0
    S

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


  • 0
    S

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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.