Another example of a thinking process to get the answer

  • 0

    At any given time i, you can either buy (or hold, if you already bought), sell, or rest. Given that you Hold, Sell, or Buy at time i, then your times i-1 and i-2 must look like one of just a few scenarios. For each one you can write an expression of the total profit based on the change in price from i-1 to i and the total profit from other scenarios in time i-1:

             2 1
             - -
             i i i
             ↓ ↓ ↓
    hold(i)  H H H  => hold(i) = hold(i-1) + price(i) - price(i-1)
             R R H  => hold(i) = rest(i-1)
             S R H  => hold(i) = rest(i-1)
    rest(i)  R R R  => rest(i) = rest(i-1)
             S R R  => rest(i) = rest(i-1)
             H S R  => rest(i) = sell(i-1)
    sell(i)  H H S  => sell(i) = hold(i-1) + price(i) - price(i-1)
             R H S  => sell(i) = hold(i-1) + price(i) - price(i-1)

    If we are looking for the most profitable strategy overall, we want to pick the most profitable of the subproblems. We can also drop duplicates, so hold[i], sell[i] and rest[i] look like this:

    hold[i] = Math.max(hold[i-1] + prices[i] - prices[i-1], rest[i-1]);
    rest[i] = Math.max(sell[i-1], rest[i-1]);
    sell[i] = hold[i-1] + prices[i] - prices[i-1];

    Since we only ever depend on one previous value for the hold, rest, and sell arrays, we can get rid of the arrays and just use three variables for a constant space, linear time solution.

Log in to reply

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