Skip to main content
CodePeetCodePeet
CodePeet 250

Best Time to Buy and Sell Stock II

MEDIUMProblemSolveExternal Links

Description

You are given an integer array prices where prices[i] represents the price of a given stock on the i-th day.

On each day, you may choose to buy or sell the stock. You can hold at most one share of the stock at any time. However, you are allowed to buy and sell multiple times — there is no limit on the number of transactions.

Your goal is to find the maximum total profit you can achieve. Note that you must sell a stock before buying again (you cannot hold multiple shares simultaneously).

Examples

Example 1

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

Output: 7

Explanation: Buy on day 1 (price = 1) and sell on day 2 (price = 5) for a profit of 5 - 1 = 4. Then buy on day 3 (price = 3) and sell on day 4 (price = 6) for a profit of 6 - 3 = 3. Total profit = 4 + 3 = 7. Notice that buying on day 1 and selling on day 4 would give 6 - 1 = 5, which is less than 7. Making two separate transactions captures more profit because we avoid the dip from 5 to 3.

Example 2

Input: prices = [1, 2, 3, 4, 5]

Output: 4

Explanation: Buy on day 0 (price = 1) and sell on day 4 (price = 5) for a profit of 5 - 1 = 4. Alternatively, buying and selling every consecutive day (1→2, 2→3, 3→4, 4→5) yields (1) + (1) + (1) + (1) = 4, which is the same. When prices strictly increase, one long transaction equals many short ones.

Example 3

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

Output: 0

Explanation: Prices only decrease every day. There is no opportunity to buy low and sell high, so the maximum profit is 0. The best strategy is to do nothing.

Constraints

  • 1 ≤ prices.length ≤ 3 × 10^4
  • 0 ≤ prices[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward approach is to explore every possible combination of buy-sell transactions using recursion. At each day, we have a choice: if we don't hold a stock, we can either buy or skip. If we hold a stock, we can either sell or skip. By trying all combinations, we find the one that maximizes total profit.

Imagine you have a time machine and can revisit the stock market. You would try every possible sequence of trades — buy on day 1 sell on day 3, buy on day 4 sell on day 5, and so on — then pick whichever sequence earned the most money. That exhaustive trial is exactly what the brute force recursion does.

We model this as a recursive function with two parameters: the current day index and whether we currently hold a stock. At each state, we branch into two choices (buy/skip or sell/skip) and return the maximum profit achievable from that point onward.

Step-by-Step Explanation

Let's trace a partial execution with prices = [7, 1, 5, 3, 6, 4]:

Step 1: Start at day 0, not holding stock. Two choices: buy at price 7, or skip.

Step 2: Try skipping day 0. Move to day 1, still not holding.

Step 3: At day 1, price is 1 (low). Try buying: pay 1, now holding stock. Move to day 2.

Step 4: At day 2, holding stock, price is 5. Try selling: gain 5, profit so far = 5 - 1 = 4. Now not holding. Move to day 3.

Step 5: At day 3, not holding, price is 3. Try buying: pay 3. Move to day 4.

Step 6: At day 4, holding, price is 6. Try selling: gain 6, profit from this trade = 6 - 3 = 3. Move to day 5.

Step 7: At day 5, not holding. No more days to trade. This path's total profit = 4 + 3 = 7.

Step 8: The recursion also explores other paths (e.g., buy day 0 sell day 2, buy day 1 sell day 4, etc.) and returns the maximum across all paths, which is 7.

The recursion tree grows exponentially because at each day we branch into two choices.

Algorithm

  1. Define a recursive function solve(day, holding) where day is the current index and holding is a boolean indicating whether we own a stock.
  2. Base case: If day >= n, return 0 (no more days to trade).
  3. If not holding:
    • Option A (skip): solve(day + 1, false)
    • Option B (buy): -prices[day] + solve(day + 1, true)
    • Return max(A, B)
  4. If holding:
    • Option A (skip): solve(day + 1, true)
    • Option B (sell): prices[day] + solve(day + 1, false)
    • Return max(A, B)
  5. Call solve(0, false) for the answer.

Code

class Solution {
public:
    int solve(vector<int>& prices, int day, bool holding) {
        if (day >= prices.size()) return 0;
        
        int skip = solve(prices, day + 1, holding);
        int action;
        if (holding) {
            action = prices[day] + solve(prices, day + 1, false);
        } else {
            action = -prices[day] + solve(prices, day + 1, true);
        }
        return max(skip, action);
    }
    
    int maxProfit(vector<int>& prices) {
        return solve(prices, 0, false);
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        def solve(day: int, holding: bool) -> int:
            if day >= len(prices):
                return 0
            
            skip = solve(day + 1, holding)
            if holding:
                action = prices[day] + solve(day + 1, False)
            else:
                action = -prices[day] + solve(day + 1, True)
            
            return max(skip, action)
        
        return solve(0, False)
class Solution {
    private int solve(int[] prices, int day, boolean holding) {
        if (day >= prices.length) return 0;
        
        int skip = solve(prices, day + 1, holding);
        int action;
        if (holding) {
            action = prices[day] + solve(prices, day + 1, false);
        } else {
            action = -prices[day] + solve(prices, day + 1, true);
        }
        return Math.max(skip, action);
    }
    
    public int maxProfit(int[] prices) {
        return solve(prices, 0, false);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each of the n days, we make two recursive calls (skip or act). This creates a binary recursion tree of depth n, giving 2^n total calls in the worst case. With n up to 3 × 10^4, this is astronomically slow.

Space Complexity: O(n)

The recursion stack goes n levels deep (one level per day), so the space used is proportional to the number of days.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^n). With n up to 30,000, this would take more operations than there are atoms in the observable universe — clearly impractical.

The core problem is that the recursion explores the same subproblems repeatedly. For example, the state (day=3, holding=false) might be reached via many different paths (buy-sell on days 0-2, or skip all of days 0-2), but each time we recompute the answer from scratch.

This overlapping subproblems pattern suggests dynamic programming as the next step: we can memoize the results of each (day, holding) state to avoid redundant computation.

Better Approach - Dynamic Programming

Intuition

The key observation from the brute force is that there are only n × 2 distinct states: for each of the n days, we are either holding a stock or not. If we store the result of each state the first time we compute it, we never recompute it. This is memoization, or top-down dynamic programming.

We can also think of it bottom-up: define two arrays (or variables):

  • notHolding[i] = maximum profit at end of day i if we do NOT hold a stock
  • holding[i] = maximum profit at end of day i if we DO hold a stock

The transitions are:

  • notHolding[i] = max(notHolding[i-1], holding[i-1] + prices[i]) — either we didn't hold yesterday and do nothing, or we held yesterday and sell today.
  • holding[i] = max(holding[i-1], notHolding[i-1] - prices[i]) — either we held yesterday and keep holding, or we didn't hold yesterday and buy today.

The answer is notHolding[n-1] since ending without holding is always at least as good as ending while holding.

Step-by-Step Explanation

Let's trace with prices = [7, 1, 5, 3, 6, 4]:

Step 1: Initialize: notHolding[0] = 0 (no stock, no trades), holding[0] = -7 (bought at price 7).

Step 2: Day 1 (price = 1):

  • notHolding[1] = max(notHolding[0], holding[0] + 1) = max(0, -7 + 1) = max(0, -6) = 0
  • holding[1] = max(holding[0], notHolding[0] - 1) = max(-7, 0 - 1) = max(-7, -1) = -1

Step 3: Day 2 (price = 5):

  • notHolding[2] = max(0, -1 + 5) = max(0, 4) = 4
  • holding[2] = max(-1, 0 - 5) = max(-1, -5) = -1

Step 4: Day 3 (price = 3):

  • notHolding[3] = max(4, -1 + 3) = max(4, 2) = 4
  • holding[3] = max(-1, 4 - 3) = max(-1, 1) = 1

Step 5: Day 4 (price = 6):

  • notHolding[4] = max(4, 1 + 6) = max(4, 7) = 7
  • holding[4] = max(1, 4 - 6) = max(1, -2) = 1

Step 6: Day 5 (price = 4):

  • notHolding[5] = max(7, 1 + 4) = max(7, 5) = 7
  • holding[5] = max(1, 7 - 4) = max(1, 3) = 3

Result: notHolding[5] = 7.

DP State Transitions — Tracking Holding vs Not Holding — Watch how we compute the maximum profit for each day in two states: holding a stock and not holding a stock, using the previous day's values.

Algorithm

  1. Initialize notHolding = 0 (start with no stock and no profit)
  2. Initialize holding = -prices[0] (if we buy on day 0)
  3. For each day i from 1 to n-1:
    • newNotHolding = max(notHolding, holding + prices[i])
    • newHolding = max(holding, notHolding - prices[i])
    • Update notHolding = newNotHolding, holding = newHolding
  4. Return notHolding

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int notHolding = 0;
        int holding = -prices[0];
        
        for (int i = 1; i < n; i++) {
            int newNotHolding = max(notHolding, holding + prices[i]);
            int newHolding = max(holding, notHolding - prices[i]);
            notHolding = newNotHolding;
            holding = newHolding;
        }
        
        return notHolding;
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        not_holding = 0
        holding = -prices[0]
        
        for i in range(1, len(prices)):
            new_not_holding = max(not_holding, holding + prices[i])
            new_holding = max(holding, not_holding - prices[i])
            not_holding = new_not_holding
            holding = new_holding
        
        return not_holding
class Solution {
    public int maxProfit(int[] prices) {
        int notHolding = 0;
        int holding = -prices[0];
        
        for (int i = 1; i < prices.length; i++) {
            int newNotHolding = Math.max(notHolding, holding + prices[i]);
            int newHolding = Math.max(holding, notHolding - prices[i]);
            notHolding = newNotHolding;
            holding = newHolding;
        }
        
        return notHolding;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the prices array once, performing O(1) work per day (two max comparisons and variable updates). Total: n iterations.

Space Complexity: O(1)

We use only two variables (notHolding and holding) instead of arrays. Since we only need the previous day's values to compute today's, we don't need to store the entire DP table.

Why This Approach Is Not Efficient

The DP approach is already O(n) time and O(1) space, so it is efficient. However, it requires reasoning about two states (holding and not holding) and understanding DP transitions, which can feel like overkill for this particular problem.

There is an even simpler insight: since we can make unlimited transactions and there is no transaction fee or cooldown, the maximum profit is simply the sum of all consecutive price increases. Every time the price goes up from one day to the next, we capture that gain. This leads to an elegant greedy solution that is equally O(n) time and O(1) space but is far simpler to understand and implement.

Optimal Approach - Greedy (Accumulate All Gains)

Intuition

Here is the key insight that makes this problem elegant: since we can buy and sell with no restrictions on the number of transactions, we should capture every single upward price movement.

Imagine you are walking along a price chart drawn on paper. Every time the line goes up (even slightly), you earn that amount. Every time it goes down, you skip it. Your total profit is the sum of all upward segments.

Mathematically, if prices go [1, 5, 3, 6], the total profit from optimal trading is:

  • 1→5: gain 4
  • 5→3: skip (price drops)
  • 3→6: gain 3
  • Total: 7

This is equivalent to: sum of max(0, prices[i] - prices[i-1]) for all i from 1 to n-1.

Why does this work? Any multi-day profit (buy at day a, sell at day b) can be decomposed into a sum of consecutive daily gains: prices[b] - prices[a] = (prices[a+1] - prices[a]) + (prices[a+2] - prices[a+1]) + ... + (prices[b] - prices[b-1]). By adding only the positive daily differences, we automatically capture exactly the profitable segments and skip the unprofitable ones.

Step-by-Step Explanation

Let's trace with prices = [7, 1, 5, 3, 6, 4]:

Step 1: Initialize profit = 0.

Step 2: Compare day 1 vs day 0: prices[1] - prices[0] = 1 - 7 = -6. Negative → skip. profit = 0.

Step 3: Compare day 2 vs day 1: prices[2] - prices[1] = 5 - 1 = 4. Positive → add! profit = 0 + 4 = 4.

Step 4: Compare day 3 vs day 2: prices[3] - prices[2] = 3 - 5 = -2. Negative → skip. profit = 4.

Step 5: Compare day 4 vs day 3: prices[4] - prices[3] = 6 - 3 = 3. Positive → add! profit = 4 + 3 = 7.

Step 6: Compare day 5 vs day 4: prices[5] - prices[4] = 4 - 6 = -2. Negative → skip. profit = 7.

Result: Return 7.

Greedy — Accumulate Every Upward Price Movement — Watch how we simply add every positive consecutive price difference to our profit. No complex state tracking — just compare adjacent days.

Algorithm

  1. Initialize profit = 0
  2. For each day i from 1 to n-1:
    • If prices[i] > prices[i-1] (price went up):
      • Add prices[i] - prices[i-1] to profit
  3. Return profit

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
};
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit
class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the prices array exactly once, making a single comparison and at most one addition per element. With n up to 3 × 10^4, this runs in microseconds.

Space Complexity: O(1)

We use only a single variable profit to accumulate the result. No additional data structures, no recursion stack — just one pass through the input.