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.