Why buying on day i and selling it on day i+1 if P[day i + 1] > P[day i] gauruntees optmiality


  • 5
    L

    Here is an explanation why

    Best time to buy and sell stocks II
    This time, multiple transactions are allowed with an exception that these transactions must not overlap. meaning once you buy, you must sell before you can buy again.

    Observations

    1. If you buy on day i and sell it on day j, (i < j) you may not make the greatest profit during that time window, as there might be day k (i < k < j) where P[day k] > P[day j]. you need to sell earlier.

    2. if you buy on day i and sell it on day j (i < j), you may not make the greatest profit POSSIBLE with that stock because there might be day k (i < k < j) where P[day k] > P[day j]. you are better off if you hold off and sell it on day k

    Optimality is garunteed if we avoid the two suboptimal transactions mentioned above

    Combining these two observations, we observe that this problem boils down to capturing all the positive differences between day[i] and day[i + 1] if and only if P[day i+1] > P[day i].

    This avoids the mistake of observation 1 (because you would have sold on day k already)

    and essentially cancels out unnecessary transactions in case of observation 2. If you buy on day i and if P[day i + 2 ] > P[day i + 1]. conditions are satisfied and you end up doing the following

    total profit = (P[day i + 1] - P[day i]) + (P[day i + 2] - P[day i + 1]) = P[day i + 2] - P[day i], thus ensuring the maximum profit for the stock bought on day[i]

    comment if you still have questions


  • 3
    M

    The only problem I can see in this algorithm is a possible misinterpretation of the rules. Depending on how you interpret them, "must sell before you can buy again" could mean you could sell the stock, then buy again on the same day as in this solution, but could also be interpreted as you can do up to one operation per day, either buy or sell, which prevents this solution in its current form.

    Of course the answer to that is to mark the start of a chunk at i where P[i+1] > P[i] and P[i] < P[i-1] and advancing a second marker j so long as P[j+1] >= P[j]. Once P[j+1] < O[j], you add (P[j] - P[i]) at that point and mark i = j = j+1. You also add the chunk when j+1 is P.length. By using markers in the algorithm instead of always adding a days profit (a sell and possible buy) in each day, it reduces to a buy, a sell, or no transaction each day, using the algorithm, but following the stricter interpretation of the "sell before you buy" restriction.

    This algorithm uses the same proof of optimality, but stores the chains of buy-both-both-both-both-sell as one transaction that is only added to the total profit once you have a buy and a sell, changing it to buy-noop-noop-noop-noop-sell.


  • 0
    L

    Agree. My proof:

    for an ascending squence, the answer is prices[last] - price[0]. as prices[j] - price[i] = price[i+1] - price[i] + price[i+2]-price[i+1] ... + price[last] - price[last-1]

    for any squence, if there's no sub sequence that is acending, then profit is 0

    if there's a longest sub sequence, p[i] to p[j], then p[j+1] will less than p[j]

    if there's another sub ascending sequence after p[j+1] say p[m] ~ p[n], then, p[j+1] ~ p[m] is a descending sequence which won't have profit.

    sub conclusion: only ascending sequence will have profit. Descending sequence won't have profit. And multiple ascending sequences won't impact each other: Proof: say i~j, m~n is 2 adjacent ascending sequence then j~m should be an descending sequence if they will impact on each other, this mean we won't sell on j then there should be another x: m <= x <= n that p[x] - p[i] > p[m] - p[n] + p[j] - p[i] as p[x] <= p[n] then p[n] - p[i] > p[n] - p[m] + p[j] - p[i] then p[j] - p[m] < 0 => p[m] > p[j] which is impossible as j~m is descend


  • 0
    L

    Firstly, I thought the same as you and I think it's ambiguous. But take the fact into consideration, if you buy on day i and sell on day j, day j must have a high price in a sub range and day j+1 has a low price, then why don't buy on day j+1 and sell someday.

    And if we sell on day j and buy on day j, it will mean that we do nothing on day j. After then, I think such 2 kinds of understanding of the question resulted in same result. So I don't think it's ambiguous now.


Log in to reply
 

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