Why the greedy algorithm works (pairwise differences only)?

  • 10


    I'd like to know why the greedy algorithm that takes pairwise profits if they are positive only?


  • 7

    You make profit by buying low and selling high, so a person would buy at trough and sell at crest, here the subtle thing is it is equivalent to buying at i and selling at i + 1 as long as price is increasing, this is fine because you can do as many transactions as you want.

    Suppose the prices are

    1  2  3  4  5

    then 5 - 1 == 2 - 1 + 3 - 2 + 4 - 3 + 5 - 4

  • 0
    This post is deleted!

  • 11

    That explanation is misleading: you sell at i+1, then i+2 price is increasing then you actually buy at i+1 and sell i+2 again, thus you buy and sell in same day.

    The proper explanation is that the calculation just accumulate you daily gains but doesn't actually sell the stock, if you buy at i, and i+1, i+2 is increasing,

    the profit so far = (prices[i+1] - prices[i]) + (prices[i+2] - prices[i+1]) 
                      = prices[i+2] - prices[i]

    You are always adding daily difference, thus you are always calculating the difference between current price and buy price in history.

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0

    What about this price sequence, 1 2 4 3 9 6 0 5? According to the algorithm I would get -1+2-2+4-4+9-9+5 = 5-1, while 9-1 is a better solution.

  • 0

    the answer should be 9-1 = 2-1 +4-2 +9-4

  • 3

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

  • 0

    @jiu9x9uij For [1 2 4 3 9 6 0 5] this sequence, the algorithm considers these cases
    (2-1) + (4-2) + (9-3) + (5-0) = 14

  • 2

    the distances between the points are always equals

Log in to reply

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