Every day you can only be in one of 2 possible states - you can either own or not own the stock. You can draw this as a diagram, where the dots represent the states you can be in at the end of the day, and the arrows indicate the options you have (buy/sell/hold):

0. Problem

To solve this problem, we want to find the maximum profit we can make in the own and not own state on the last day. We'll call this O(n-1) and N(n-1).

1. Recursion

To find the recursion for the Own state O(i), you have to consider all the ways of getting to the Own state on day i. Here's a visual of this:

The first way to get to the Own state is to stay in the Own state, keeping the profit we had on the previous day O(i-1). The other way to get to the Own state is to come from the Not Own state, where we keep our profit from the previous day N(i-1), and then we buy the stock for prices[i] dollars, giving us a total profit of N(i-1) - prices[i].

Those are the 2 possible profits we can have in the Own state on day i. To get the value of O(i), we can take whichever is bigger:

You can use a similar process to find the max profit in the Not Own state:

These are our two recursions.

2. Base case

The recursions keep getting called on earlier days until they eventually reach O(-1) and N(-1). This is where the recursions break, so we have to manually set these values.

We know N(-1) = 0, because we start out in the Not Own state on day -1 with 0 proft. But what should we set O(-1) equal to? We can't possibly be in the Own state on day -1, so it doesn't really make sense to set a value for this state. It turns out we can simply set O(-1) = -infinity so that the value gets ignored in the recursion. Here are the base cases:

3. Code

These functions will make many of the same calls multiple times if we just code them up like normal recursive functions. This means we need to use Dynamic Programming to optimize them.

O(i) and N(i) only depend on O(i-1) and N(i-1), so we can compute small i first and big i last. We can save space by only remembering the previous day's max profits. This is called "Tabulation+". Here's the code:

Time Complexity $O(n)$

Space Complexity $O(1)$. We store two numbers $\tt O$ and $\tt N$, which is $O(2) = O(1)$.

Here are suboptimal solutions you might come up with first:

Open Spoiler

Naive Recursion

Open Spoiler

Time Complexity $O(2^n)$:

Space Complexity $O(n)$ for the Call Stack.

Memoization

Open Spoiler

Time Complexity $O(n)$

Space Complexity $O(n)$ for the Call Stack and for memo

Tabulation

Open Spoiler

Notice that we only ever compute the current day's B(i) and S(i) using the previous day's B(i-1) and S(i-1). This means we can compute profits of the earlier days first and the later days last.

Time Complexity $O(n)$

Space Complexity $O(n)$ for S and B