Best Time to Buy and Sell Stock II — Unlimited Transactions State Machine

Problem Statement#

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.

Constraints:

• 1 <= prices.length <= 3 * 10^4
• 0 <= prices[i] <= 10^4

Example 1:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buy day 2 (price=1), sell day 3 (price=5), profit = 4.
             Buy day 4 (price=3), sell day 5 (price=6), profit = 3.
             Total profit = 4 + 3 = 7.

Example 2:

Input:  prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: Buy day 1 (price=1), sell day 5 (price=5). Or equivalently,
             collect every adjacent positive slope: (2-1)+(3-2)+(4-3)+(5-4) = 4.

Example 3:

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices only decrease — no profitable transaction.

Why This Problem Matters#

Stock II is the "unlimited transactions" variant that naturally follows Stock I in FAANG interviews. It tests two insights:

1. Greedy insight: With unlimited transactions, you can capture every upward price movement. Collect all positive differences prices[i+1] - prices[i] and ignore negatives.

2. State machine DP insight: The only structural change from Stock I is in the "buy" transition — after selling, you can buy again. This changes hold = max(hold, -price) to hold = max(hold, cash - price). The rest of the state machine is identical.

Understanding both approaches is important. The greedy solution is O(n) and trivially correct. The state machine is equally efficient and demonstrates how unlimited transactions fit into the broader DP framework — critical for explaining how to scale to LC 123, LC 188, and LC 309.

The Core Insight#

Greedy / slope-collection approach: With unlimited transactions, every upward slope is profitable to capture. If prices[i+1] > prices[i], add the difference. This is equivalent to buying and selling on consecutive days whenever there's a profit.

Why this works: A longer profitable trade (buy day 1, sell day 4) can always be decomposed into smaller consecutive profitable trades without losing any profit: (p4 - p1) = (p2-p1) + (p3-p2) + (p4-p3). So collecting every positive adjacent difference is equivalent to the best multi-day trade.

State machine DP formulation:

Two states: hold (holding stock) and cash (not holding).

Key difference from Stock I:

• Stock I: hold = max(hold, -price) — only ever buy once (no cash accumulation before buying)
• Stock II: hold = max(hold, cash - price) — can use accumulated cash to fund a new buy

Transitions:

hold = max(hold, cash - price)   # keep holding OR buy today using current cash
cash = max(cash, hold + price)   # stay out OR sell today

Base cases: hold = -infinity, cash = 0

Answer: cash after processing all days.

Building the DP Solution#

Approach 1 — Greedy (simplest for unlimited transactions):

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

O(n) time, O(1) space.

Approach 2 — State machine DP:

def maxProfit(prices):
    hold = float('-inf')
    cash = 0
    for price in prices:
        prev_cash = cash
        cash = max(cash, hold + price)
        hold = max(hold, prev_cash - price)
    return cash

Note: We save prev_cash before updating cash, to use it in the hold update. This avoids using the same day's sell profit to immediately re-buy on the same day (though the problem allows same-day buy/sell — this distinction does not change the answer because profit nets to 0).

Visual Dry Run#

Input: prices = [7, 1, 5, 3, 6, 4]

State machine trace:

Answer: cash = 7

Greedy trace:

Both give 7.

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # State machine: hold = best profit while holding
        #                cash = best profit while not holding
        hold = float('-inf')
        cash = 0
 
        for price in prices:
            prev_cash = cash
            # Sell today: take the better of keeping cash or selling now
            cash = max(cash, hold + price)
            # Buy today: use previous day's cash (not today's — avoids buy-sell-buy on same price)
            hold = max(hold, prev_cash - price)
 
        return cash

JavaScript#

var maxProfit = function(prices) {
    let hold = -Infinity;
    let cash = 0;
 
    for (const price of prices) {
        const prevCash = cash;
        cash = Math.max(cash, hold + price);   // sell or rest
        hold = Math.max(hold, prevCash - price); // buy or keep holding
    }
 
    return cash;
};

Complexity Analysis#

Common Mistakes#

1. Confusing unlimited transactions with buying multiple shares. You can only hold at most 1 share at a time. "Unlimited transactions" means you can sell and re-buy — not that you can stack multiple shares. Each transaction is still one buy followed by one sell.

2. In the state machine, using the current day's cash to buy on the same day. If you update cash first, then use the updated cash to compute hold, you simulate using today's sell profit to immediately re-buy on the same day. This does not change the final answer (profit nets to 0 on same-day buy-sell), but using prev_cash is conceptually cleaner.

3. Forgetting to collect negative slopes in the greedy approach — but that's actually correct. The greedy approach adds only positive differences. You do NOT add negative differences. This is the correct behavior — no profitable trade exists on downward days.

4. Comparing Stock II greedy to Stock I running minimum. Stock I needs the running minimum because you're choosing the best single buy-sell pair globally. Stock II is simpler: collect every upward slope locally. The two algorithms are fundamentally different even though both are O(n)/O(1).

5. In the state machine, initializing hold = 0 instead of -infinity. hold = 0 means "holding a stock worth 0 profit" — treating the stock as if it was obtained for free. The correct initialization is hold = -infinity meaning "no stock held yet — unreachable state."

Interview Tips#

• Present both approaches clearly: "The greedy approach sums all positive adjacent differences. The state machine DP is hold = max(hold, cash - price) and cash = max(cash, hold + price) — just one character different from Stock I."
• Highlight the key difference from Stock I: "In Stock I, we can only buy once so hold = max(hold, -price). In Stock II, we can re-buy after selling so hold = max(hold, cash - price) — the cash variable carries our accumulated profit forward."
• Verify on the increasing array [1,2,3,4,5]: greedy gives (2-1)+(3-2)+(4-3)+(5-4) = 4; state machine gives 4. Both correct.
• Connect to the series: "This state machine extends to Stock III by tracking two independent hold/sell pairs, and to Stock IV by generalizing to k pairs."

Follow-up Questions#

Q: What is the difference in the recurrence between Stock I and Stock II? Stock I: hold = max(hold, -price) — buy only once, never using accumulated cash. Stock II: hold = max(hold, cash - price) — re-buy after selling, using accumulated cash.

Q: What if you can buy only k times total? (LC 188) Track k buy/sell state pairs: dp[t][0] = cash after t complete transactions not holding, dp[t][1] = cash after t-1 complete transactions while holding. Update all k pairs each day.

Q: What is the maximum profit you can make with exactly 2 transactions? (LC 123) Track 4 state variables: buy1, sell1, buy2, sell2. buy2 = max(buy2, sell1 - price) allows the second buy to use the first sell's profit.

Q: Is the greedy always optimal for unlimited transactions? Yes. The greedy proof: any profitable multi-day trade (buy i, sell j) can be decomposed into consecutive-day trades without reducing profit. Therefore collecting every positive adjacent difference is globally optimal.

Key Takeaways#

• For unlimited transactions, the greedy insight is: collect every positive adjacent price difference — every upward slope is a profitable trade.
• The state machine DP changes exactly one character from Stock I: hold = max(hold, cash - price) instead of hold = max(hold, -price). This allows re-buying after selling.
• Save prev_cash before updating cash to correctly model that you cannot sell and re-buy using the same transaction profit on the same day.
• hold = -infinity initialization is critical — it means "no stock held yet" and prevents false profit from imaginary free stocks.
• This state machine framework — hold and cash updated each day — is the backbone for Stock III, IV, cooldown, and fee variants. LC 122 is the simplest entry point into that framework.