DP 36: Best Time to Buy and Sell Stock II — Recursion to Space Optimization

This chapter explores the second problem in the Dynamic Programming on Stocks series. Unlike the first problem—where you are restricted to buying once and selling once—this problem allows you to buy and sell as many times as you want, with the sole constraint that you must sell your currently held stock before you can buy again.

1. Problem Statement & Core Rules

You are given a 1D array prices representing the stock price on each day. Your goal is to maximize your total profit by choosing when to buy and when to sell.

Key Rules and Constraints:

Multiple Transactions Allowed: You can buy and sell multiple times.
Strict Alternation: You cannot buy a new stock if you are already holding one. You must sell your current holding before performing another buy operation.

Structure & Concept Flow
[Correct Workflow]
Day 1: Buy -> Day 3: Sell -> Day 4: Buy -> Day 5: Sell (Allowed)

[Incorrect Workflow]
Day 1: Buy -> Day 2: Buy -> Day 3: Sell (Not Allowed - double buy)

Example Walkthrough:

Consider the prices array: [7, 1, 5, 3, 6, 4]

Approach A: Buy on Day 2 (price = 1) and sell on Day 3 (price = 5) $\rightarrow$ Profit = $5 - 1 = 4$ . Then buy on Day 4 (price = 3) and sell on Day 5 (price = 6) $\rightarrow$ Profit = $6 - 3 = 3$ . Total Profit = $4 + 3 = 7$ .
Approach B: Buy on Day 2 (price = 1) and sell on Day 5 (price = 6) $\rightarrow$ Profit = $6 - 1 = 5$ .

The maximum achievable profit for this example is 7.

2. Core Mental Model & Intuition

When faced with multiple valid choices (buy, sell, or skip) at every single index to maximize a target metric, the problem naturally lends itself to Recursion.

Real-Life Analogy: The Trading Desk Workflow

Imagine standing in front of a ticker tape every morning. On any given day, you have two choices depending on your current inventory status:

If you hold no stock (buy = 1): You can either choose to buy at the current market price (spending cash, moving to a state where you must sell next) or skip/not buy and move to the next day.
If you already hold a stock (buy = 0): You can either choose to sell at the current market price (collecting cash, freeing yourself up to buy again) or hold/not sell and move to the next day.

3. Step 1: Recursive Formulation

To write a correct recurrence relation, we express the state using two changing parameters:

index: The current day we are examining (ranging from 0 to n - 1).
buy: A binary flag where 1 means we are allowed to buy, and 0 means we cannot buy (because we are currently holding a stock that must be sold first).

Recurrence Breakdown:

Base Case: When index == n (we have exhausted all days), no further transactions can be made, so the profit returned is 0.
When buy == 1 (Allowed to Buy):
- Option 1 (Take / Buy): We purchase the stock at prices[index]. This costs money, so we subtract prices[index] from our profit, and transition to (index + 1, buy = 0).
- Option 2 (Not Take / Skip): We skip buying today, add 0 profit, and transition to (index + 1, buy = 1).
- Decision: Take the max of both choices.
When buy == 0 (Not Allowed to Buy / Holding Stock):
- Option 1 (Sell): We sell the stock at prices[index]. This brings money in, so we add prices[index] to our profit, and transition to (index + 1, buy = 1).
- Option 2 (Hold / Skip Selling): We hold the stock, add 0 profit, and transition to (index + 1, buy = 0).
- Decision: Take the max of both choices.

Recursive Code Implementation:

C++

long long getAns(vector<long long>& prices, int n, int index, int buy, vector<vector<long long>>& dp) {
    // Base Case
    if (index == n) return 0;
    
    if (dp[index][buy] != -1) return dp[index][buy];
    
    long long profit = 0;
    if (buy) {
        // Choice 1: Buy the stock (-prices[index]), next we must sell (buy = 0)
        // Choice 2: Skip buying (0), next we can still buy (buy = 1)
        profit = max(-prices[index] + getAns(prices, n, index + 1, 0, dp),
                      0 + getAns(prices, n, index + 1, 1, dp));
    } else {
        // Choice 1: Sell the stock (+prices[index]), next we can buy again (buy = 1)
        // Choice 2: Hold the stock (0), next we still cannot buy (buy = 0)
        profit = max(prices[index] + getAns(prices, n, index + 1, 1, dp),
                      0 + getAns(prices, n, index + 1, 0, dp));
    }
    
    return dp[index][buy] = profit;
}

Time Complexity: $O(N \times 2)$ since there are $N$ indices and $2$ states for buy.
Space Complexity: $O(N \times 2)$ for the DP table $+ O(N)$ auxiliary recursion stack space.

4. Step 2: Tabulation (Bottom-Up DP)

To eliminate auxiliary stack space, we convert the top-down memoized solution into a bottom-up iterative table.

Tabulation Strategy:

Table Definition: dp[n + 1][2] where dp[index][buy] stores the maximum profit.
Base Case: dp[n][0] = 0 and dp[n][1] = 0 (when index reaches $n$ , profit is $0$ ).
Loop Direction: Since recursion goes from 0 to n, tabulation loops backward from index = n - 1 down to 0.

Tabulation Code Implementation:

C++

long long maximumProfit(vector<long long>& prices) {
    int n = prices.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));
    
    // Base case is already 0 initialized for dp[n][0] and dp[n][1]
    
    for (int index = n - 1; index >= 0; index--) {
        for (int buy = 0; buy <= 1; buy++) {
            long long profit = 0;
            if (buy) {
                profit = max(-prices[index] + dp[index + 1][0],
                              0 + dp[index + 1][1]);
            } else {
                profit = max(prices[index] + dp[index + 1][1],
                              0 + dp[index + 1][0]);
            }
            dp[index][buy] = profit;
        }
    }
    
    return dp[0][1]; // Starting at index 0 with buy = 1 (allowed to buy)
}

5. Step 3: Space Optimization (Using Two 1D Arrays)

Notice that computing the values at index only requires values from index + 1 (the next row). We do not need to store the entire 2D table of size $(N + 1) \times 2$ ; storing just the ahead row and the current row is sufficient.

Space-Optimized Code:

C++

long long maximumProfit(vector<long long>& prices) {
    int n = prices.size();
    vector<long long> ahead(2, 0), cur(2, 0);
    
    // Base case: ahead[0] and ahead[1] are 0 when index == n
    
    for (int index = n - 1; index >= 0; index--) {
        for (int buy = 0; buy <= 1; buy++) {
            long long profit = 0;
            if (buy) {
                profit = max(-prices[index] + ahead[0],
                              0 + ahead[1]);
            } else {
                profit = max(prices[index] + ahead[1],
                              0 + ahead[0]);
            }
            cur[buy] = profit;
        }
        ahead = cur; // Shift rows forward
    }
    
    return ahead[1];
}

Time Complexity: $O(N)$
Space Complexity: $O(1)$ (using two arrays of size 2).

6. Step 4: Ultimate Optimization (Four Variables)

Many high-performance solutions in coding forum discussions omit the inner loop and arrays entirely, replacing them with four scalar variables. This represents the absolute limit of space optimization.

Mapping Variables:

ahead_not_by corresponds to ahead[0] (cannot buy / holding stock in the previous row)
ahead_by corresponds to ahead[1] (can buy in the previous row)
cur_not_by corresponds to cur[0]
cur_by corresponds to cur[1]

Final Variable-Optimized Code:

C++

long long maximumProfit(vector<long long>& prices) {
    int n = prices.size();
    long long ahead_not_by = 0, ahead_by = 0;
    long long cur_not_by = 0, cur_by = 0;
    
    for (int index = n - 1; index >= 0; index--) {
        // When buy = 0 (cannot buy / sell state)
        cur_not_by = max(prices[index] + ahead_by, 0 + ahead_not_by);
        
        // When buy = 1 (can buy state)
        cur_by = max(-prices[index] + ahead_not_by, 0 + ahead_by);
        
        // Shift states for the next iteration
        ahead_not_by = cur_not_by;
        ahead_by = cur_by;
    }
    
    return ahead_by; // Starting at index 0 with buy allowed (ahead_by)
}

7. Complexity Summary Table

Approach	Time Complexity	Space Complexity	Auxiliary Stack Space
Recursion	$O(2^N)$	$O(1)$	$O(N)$
Memoization (DP)	$O(N \times 2)$	$O(N \times 2)$	$O(N)$
Tabulation	$O(N \times 2)$	$O(N \times 2)$	None ( $O(1)$ )
Space Optimized (2 Arrays)	$O(N)$	$O(1)$ (Size 2 arrays)	None ( $O(1)$ )
Variable Optimized (4 Variables)	$O(N)$	$O(1)$ (4 Scalars)	None ( $O(1)$ )

Summary and Key Takeaways

Problem Generalization: This problem models multi-transaction stock trading by introducing a state variable (buy) that tracks whether the trader is currently holding a stock.
Recursive Blueprint: On any given day, explore all valid choices (buy or skip when allowed; sell or hold when holding) and take the maximum profit.
Overlapping Subproblems: The recursive states (index, buy) repeat across branches, making Memoization necessary to avoid exponential time complexity.
Bottom-Up Transformation: Tabulation reverses the loop direction, eliminating the recursion overhead.
Space Reduction: Because computation at index only depends on index + 1, the 2D DP table is successfully compressed down to either two 1D vectors or four scalar variables.