0. Problem

This is the same as the previous problem, but we just have more states. Specifically, we start out not owning the stock, and can buy/sell up to k times. Here are the states:

The answer to the problem is the biggest possible profit, out of all the states we can be in.

1. Recursion

To find the recursion for each state, you just have to look at all the arrows that point to it. Looking at the above diagram, all the states look pretty much exactly the same - you can either stay a the state without doing anything. Or you can move to the next lower state, by adding or subtracting prices[i] from your profit. We also have the Not Own state, which just points to itself.

Here's the recursion when we consider this:

2. Base case

We start out in the Not Own state with 0 profit. We can't possibly be in any of the other states, so we set them to -infinity. The max profits at the very beginning when i=-1 are:

3. Code

To code this up, just combine the recursion and base cases, and use Tabulation+. We'll store all the states in an array, and update them during every timestep.

Time Complexity $O(nk)$. We iterate through all $n$ days. Every day we update $k$ states.

Space Complexity $O(k)$. We store $2k+1$ states. $O(2k + 1) = O(k)$.

You should be able to use this code to solve the previous stock problems. Just set k equal to 1,2, or n.