How to prove the method "buy today sell tomorrow only if the price tomorrow is higher" is right mathmetically?


  • 1
    S

    I know it's right, my code is accepted. But how to prove this method is mathmetically right ?


  • 0
    A

    what do you mean by drawing a trend table? does that make a proof?


  • 0
    L
    This post is deleted!

  • 0
    F

    How do you feel right now ?
    I'm confusing on the same question !!!
    How could we know the selling price before buying ??


  • 2
    B

    Consider first a contiguous subsequence of increasing prices.
    The profit-maximizing strategy within this subsequence is to buy on the first day and sell on the last day
    because this is the only strategy that realizes all of the day-to-day gains within the subsequence.

    Notice further that the entire sequence can be decomposed into a series of
    maximally-sized contiguous subsequences of increasing prices, some of which might be trivial, i.e., of length 1.
    It never makes sense to buy in one such subsequence A and then sell in a following subsequence B, since we could
    always do better by inserting a sale at the end of A and a buy at the beginning of B.

    Therefore profit can be maximized by identifying each maximally-sized contiguous subsequence of increasing prices,
    and buying at the beginning of it and selling at the end of it.

    However, there is more to the story!
    Because this strategy realizes all of the day-to-day gains within each subsequence, and we have described how
    the entire sequence can be decomposed into such subsequences, it follows that this strategy
    realizes all of the day-to-day gains within the entire sequence.
    Since we are only asked to return the total profit and not the actual transaction log,
    it suffices to sum together the day-to-day gains across the entire sequence.


Log in to reply
 

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