Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 and sell multiple times, even on the same day.

Find and return the maximum profit you can achieve.

How Is This Different From Stock I?

In Best Time to Buy and Sell Stock I, you could make only one transaction.

Here, you can make as many transactions as you want. The only rule is that you can hold at most one share at a time, so you must sell before you buy again.

We'll solve this in two ways:

1. Dynamic Programming: builds up from a simple "choose at each day" idea. This pattern also solves the harder stock problems.
2. Greedy: a short and clever trick that works for this problem.

The Key Idea: Two States

On any day, we are in one of two situations:

• canBuy = true: we don't hold a stock, so we can buy one or skip the day.
• canBuy = false: we are holding a stock, so we can sell it or skip the day.

At each day, we try both choices and keep the one that gives more profit:

1canBuy = true:
2    buy today  →  -prices[day] + profit from (day + 1, canBuy = false)
3    skip today →                 profit from (day + 1, canBuy = true)
4 
5canBuy = false:
6    sell today →  +prices[day] + profit from (day + 1, canBuy = true)
7    skip today →                 profit from (day + 1, canBuy = false)

Buying costs money, so we subtract the price. Selling earns money, so we add the price.

When we run out of days, there is no more profit to make, so the answer is 0.

We start on day 0 with canBuy = true, because we don't own any stock yet.

Approach 1: Recursion

This is a direct translation of the choices above into code.

class Solution {
    public:
    int maxProfitFrom(int day, bool canBuy, vector<int>& prices) {
        if (day == prices.size()) {
            return 0;
        }

        if (canBuy) {
            int buyToday = -prices[day] + maxProfitFrom(day + 1, false, prices);
            int skipToday = maxProfitFrom(day + 1, true, prices);
            return max(buyToday, skipToday);
        }

        int sellToday = prices[day] + maxProfitFrom(day + 1, true, prices);
        int skipToday = maxProfitFrom(day + 1, false, prices);
        return max(sellToday, skipToday);
    }

    int maxProfit(vector<int>& prices) {
        return maxProfitFrom(0, true, prices);
    }
};

Time: O(2^n), because every day makes two recursive calls.

Space: O(n) for the recursion stack.

This is correct but too slow: it solves the same (day, canBuy) situation many times.

Click to zoom

Approach 2: Memoization (Top-Down DP)

There are only n × 2 different situations: every day, with canBuy either true or false.

So we store each answer in a table the first time we calculate it. If we see the same situation again, we return the stored answer instead of recalculating it.

memo[day][canBuy] stores the best profit starting from day in that state. -1 means "not calculated yet".

class Solution {
    public:
    int maxProfitFrom(int day, bool canBuy, vector<int>& prices,
        vector<vector<int>>& memo) {
        if (day == prices.size()) {
            return 0;
        }

        if (memo[day][canBuy] != -1) {
            return memo[day][canBuy];
        }

        int bestProfit;

        if (canBuy) {
            int buyToday = -prices[day] + maxProfitFrom(day + 1, false, prices, memo);
            int skipToday = maxProfitFrom(day + 1, true, prices, memo);
            bestProfit = max(buyToday, skipToday);
        } else {
            int sellToday = prices[day] + maxProfitFrom(day + 1, true, prices, memo);
            int skipToday = maxProfitFrom(day + 1, false, prices, memo);
            bestProfit = max(sellToday, skipToday);
        }

        return memo[day][canBuy] = bestProfit;
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> memo(n, vector<int>(2, -1));
        return maxProfitFrom(0, true, prices, memo);
    }
};

Time: O(n), since each of the n × 2 states is calculated once.

Space: O(n) for the table and the recursion stack.

Approach 3: Tabulation (Bottom-Up DP)

Memoization still uses recursion. With tabulation, we fill the same table using a loop instead.

Look at the recursion: the answer for day depends only on day + 1. So we fill the table from the last day backward.

profit[day][canBuy] means the same thing as before. We use an extra row, profit[n], filled with 0, for "no days left".

class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        // profit[day][1] = best profit from 'day' when we can buy
        // profit[day][0] = best profit from 'day' when we are holding a stock
        vector<vector<int>> profit(n + 1, vector<int>(2, 0));

        for (int day = n - 1; day >= 0; day--) {
            // canBuy = true
            int buyToday = -prices[day] + profit[day + 1][0];
            int skipBuy = profit[day + 1][1];
            profit[day][1] = max(buyToday, skipBuy);

            // canBuy = false (holding)
            int sellToday = prices[day] + profit[day + 1][1];
            int skipSell = profit[day + 1][0];
            profit[day][0] = max(sellToday, skipSell);
        }

        return profit[0][1];
    }
};

Time: O(n)

Space: O(n) for the table, but no recursion stack.

Approach 4: Space Optimized DP

In the table, each row uses only the row right after it. We never look further ahead.

So instead of a full table, we keep just two numbers for "tomorrow":

• nextCanBuy: the best profit from tomorrow if we can buy.
• nextHolding: the best profit from tomorrow if we are holding a stock.

class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        int nextCanBuy = 0;
        int nextHolding = 0;

        for (int day = n - 1; day >= 0; day--) {
            int currCanBuy = max(-prices[day] + nextHolding, nextCanBuy);
            int currHolding = max(prices[day] + nextCanBuy, nextHolding);

            nextCanBuy = currCanBuy;
            nextHolding = currHolding;
        }

        return nextCanBuy;
    }
};

Time: O(n)

Space: O(1)

Approach 5: Greedy (Simplest Optimal)

Since we can trade as many times as we want, we can collect every price increase between two days in a row.

If tomorrow's price is higher than today's, buy today and sell tomorrow. If it's lower, do nothing.

class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int totalProfit = 0;

        for (int day = 1; day < prices.size(); day++) {
            if (prices[day] > prices[day - 1]) {
                totalProfit += prices[day] - prices[day - 1];
            }
        }

        return totalProfit;
    }
};

Time: O(n)

Space: O(1)

Dry Run

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

1day   price   change from yesterday   added   totalProfit
2 1      7              -                 -          0
3 2      1         1 - 7 = -6             0          0
4 3      5         5 - 1 = +4             4          4
5 4      3         3 - 5 = -2             0          4
6 5      6         6 - 3 = +3             3          7
7 6      4         4 - 6 = -2             0          7

The total profit is 7.

Why Does Greedy Work?

Think of prices as stairs. Every time the price goes up, that's a step up. Every time it goes down, that's a step down.

Our profit is the total height we climb. Going down never helps, so we skip it.

But what about one long rise? Look at prices = [1,2,3,4,5]:

1One big trade:      buy at 1, sell at 5   →  5 - 1 = 4
2Daily small trades: (2-1) + (3-2) + (4-3) + (5-4) = 1 + 1 + 1 + 1 = 4

Both give the same profit. Climbing one big staircase is the same as climbing each step one by one. So adding up every daily rise always gives the maximum profit.

The greedy code doesn't describe the exact trades a person would make, but it always finds the correct total profit.

Comparing All Approaches

Complexity

How to Explain It in an Interview