0. Problem

In this problem, you start out not owning the stock. You can buy/sell it the 1st time, or buy/sell it the 2nd time.

This is a total of 5 states. Every day you can stay in your current state, or move to a different one like this:

We're looking for the max profit in any of these states on the last day.

1. Recursion

To find a recursion for each state, you can look at all the arrows that point to it:

2. Base case

The recursion eventually gets to i=-1. This is when the recursion needs to stop, since there are no previous days' stock prices. We start not owning the stock and with 0 profit. We can't reach the other states yet on the first day, so we just set their profits to -infinity so they'll get overwritten when we finally can reach them.

3. Code

Combining the recursion and base case, and using "Tabulation+", we get:

Time Complexity $O(n)$. We loop though an array.

Space Complexity $O(1)$. We store 5 variables.