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:

N(i) = N(i-1)                               # hold
O1(i) = max(O1(i-1), N(i-1) - prices[i])    # hold or buy
S1(i) = max(S1(i-1), O1(i-1) + prices[i])   # hold or sell
O2(i) = max(O2(i-1), S1(i-1) - prices[i])   # hold or buy
S2(i) = max(S2(i-1), O2(i-1) + prices[i])   # hold or sell

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.

N(-1) = 0
O1(-1) = float('-inf')
S1(-1) = float('-inf')
O2(-1) = float('-inf')
S2(-1) = float('-inf')

3. Code

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

def twoshotProfit(prices):
    # day -1
    N = 0
    O1 = float('-inf') # -infinity
    S1 = float('-inf')
    O2 = float('-inf')
    S2 = float('-inf')

    # day 0, 1, ..., n-1
    for i in range(len(prices)): 
        (N, O1, S1, O2,  S2) = (
            N,
            max(O1, N - prices[i]),
            max(S1, O1 + prices[i]),
            max(O2, S1 - prices[i]),
            max(S2, O2 + prices[i])
        )

    return max(N, O1, S1, O2, S2)

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

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