Best Time to Buy and Sell Stock II

we can buy any number of stocks but we cannot buy 2 stocks at a same time

Best Time to Buy and Sell Stock II

Problem

You are given an array prices. The value prices[i] is the price of a stock on day i.

On each day, you can buy and/or sell the stock. But you can hold only one share at any time. You can buy and sell many times, even on the same day.

Return the maximum profit you can get.

Examples

Example 1

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

• Buy on day 2 (price = 1) and sell on day 3 (price = 5). Profit = 5 - 1 = 4.
• Buy on day 4 (price = 3) and sell on day 5 (price = 6). Profit = 6 - 3 = 3.
• Total profit = 4 + 3 = 7.

Example 2

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

• Buy on day 1 (price = 1) and sell on day 5 (price = 5).
• Total profit = 5 - 1 = 4.

Example 3

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

• The price only goes down, so we never buy.
• The maximum profit is 0.

Main Idea

On each day, we are in one of two states. We use a variable buy to track this:

• buy = 1: We do not hold a stock. We are allowed to buy.
• buy = 0: We hold a stock. We are allowed to sell.

On each day, we have two choices.

When we are allowed to buy (buy = 1):

• Pick: Buy today. We pay prices[index], so we add -prices[index]. Then we move to the next day with buy = 0.
• Not pick: Do nothing. We move to the next day with buy = 1.

When we are allowed to sell (buy = 0):

• Pick: Sell today. We get prices[index]. Then we move to the next day with buy = 1.
• Not pick: Do nothing. We move to the next day with buy = 0.

We take the maximum of both choices.

Base Case

• If index === n, the days are over. We cannot earn any more money, so return 0.

Example: How It Works

Let us take prices = [7, 1, 5].

• Day 0 (price 7), can buy:
  • Buy: -7 and then continue with the next day in sell state.
  • Skip: continue with the next day in buy state.
• Day 1 (price 1), can buy:
  • Buy: -1 and then continue with day 2 in sell state.
  • On day 2, we can sell at 5. Profit = -1 + 5 = 4.
• The best path is to skip day 0, buy on day 1 and sell on day 2.

So the answer is 4.

Solution 1: Recursion + Memoization (Top-Down)

We write a recursive function and save each answer in a table. The table is dp[index][buy]. So we never solve the same problem twice.

var maxProfit = function (prices) {
    let n = prices.length;

    let capital = 0;

    let dp = Array.from({ length: n }, () => Array(2));

    function recurr(index, buy) {
        // all days are over
        if (index === n) {
            return 0;
        }

        // answer is already saved
        if (dp[index][buy] !== undefined) {
            return dp[index][buy];
        }

        if (buy) {
            // we can buy: buy today OR skip today
            let pick = -prices[index] + recurr(index + 1, 0);
            let notPick = recurr(index + 1, 1);

            capital = Math.max(pick, notPick);
        } else {
            // we can sell: sell today OR skip today
            let pick = prices[index] + recurr(index + 1, 1);
            let notPick = recurr(index + 1, 0);

            capital = Math.max(pick, notPick);
        }

        dp[index][buy] = capital;
        return capital;
    }

    return recurr(0, 1);
};

Tip: The variable capital is shared by all calls. It works here, because we save and return it right after we set it. But it is safer to declare it with let inside the function.

Complexity

• Time Complexity: O(n)
  • n is the number of days.
  • There are n * 2 different states, and each state is solved only once.
• Space Complexity: O(n)
  • The dp table stores n * 2 values.
  • The recursion stack also uses O(n) extra space.

Solution 2: Tabulation (Bottom-Up)

In this method, we do not use recursion. We start from the last day and move to the first day.

Here, dp[index][buy] means: the maximum profit we can make from day index to the end, in the state buy.

var maxProfit = function (prices) {
    let n = prices.length;

    let capital = 0;

    let dp = Array.from({ length: n + 1 }, () => Array(2));

    // base case: no days left, so no profit
    dp[n][0] = 0;
    dp[n][1] = 0;

    for (let index = n - 1; index >= 0; index--) {
        for (let buy = 0; buy <= 1; buy++) {
            if (buy) {
                // we can buy: buy today OR skip today
                let pick = -prices[index] + dp[index + 1][0];
                let notPick = dp[index + 1][1];

                capital = Math.max(pick, notPick);
            } else {
                // we can sell: sell today OR skip today
                let pick = prices[index] + dp[index + 1][1];
                let notPick = dp[index + 1][0];

                capital = Math.max(pick, notPick);
            }

            dp[index][buy] = capital;
        }
    }

    // start from day 0, and we are allowed to buy
    return dp[0][1];
};

Complexity

• Time Complexity: O(n)
  • We use one loop over the days. The inner loop runs only 2 times.
  • Each cell is filled in constant time.
• Space Complexity: O(n)
  • The dp table has (n + 1) * 2 cells.
  • There is no recursion stack.

Comparison

Summary

• This is a dynamic programming problem with two states: can buy and can sell.
• On each day, we have two choices: do the action (buy or sell) or skip the day.
• When we buy, we subtract the price. When we sell, we add the price.
• We always take the maximum of both choices.
• Both solutions run in O(n) time and use O(n) space.
• Tabulation avoids recursion, so it is safer for long arrays.