Best Time to Buy and Sell Stock II

Medium15–20 min

Topics

Dynamic ProgrammingGreedy

Companies

AmazonMicrosoftBloomberg

Given the daily `prices` of a stock, you may buy and sell as many times as you like — but you can never hold more than one share at a time, so you must sell (or already be holding nothing) before buying again. Maximize the total profit across every trade you make. The single-transaction version of this problem tracks one running minimum and one running best-so-far. This version removes the "only once" restriction, which changes the shape of the answer entirely: with unlimited trades and no cost per trade, the best possible total is simply the sum of every day-to-day price increase in the whole sequence. Any stretch where the price climbs for several days in a row contributes the same total either way — bought once at the bottom and sold once at the top, or split into several smaller back-to-back trades along the way — so there's no benefit to ever holding through a day where the price is about to drop.

Test Case 1:

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

Output:7

Explanation:Buy at 1, sell at 5 (+4); buy again at 3, sell at 6 (+3). Two separate round trips, 4 + 3 = 7 total — better than trying to hold from the very bottom to the very top in one trade.

Test Case 2:

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

Output:4

Explanation:Prices climb every single day, so one long hold from day 0 to day 4 captures the whole 5 − 1 = 4 rise — no benefit to splitting it into smaller trades here.

Test Case 3:

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

Output:0

Explanation:Prices only ever fall. Every possible buy day is more expensive than every later sell day, so the best move is to never trade at all.

Constraints

◆1 ≤ prices.length ≤ 12
◆0 ≤ prices[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Walk the days one at a time, and at every day ask what state you're in: are you currently holding a share or not? From either state there are two live choices — do nothing and move on, or act (buy if you're empty-handed, sell if you're holding) and move on. Trying both choices at every single day and keeping the better outcome is correct, but the same (day, holding) situation gets rediscovered through many different sequences of past choices, so the work roughly doubles with every extra day.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] prices;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        return solve(0, false);
    }

    private int solve(int day, boolean holding) {
        if (day == prices.length) return 0;
        int doNothing = solve(day + 1, holding);
        int act;
        if (holding) {
            act = prices[day] + solve(day + 1, false);
        } else {
            act = -prices[day] + solve(day + 1, true);
        }
        return Math.max(doNothing, act);
    }
}

Optimal — Greedy Sum of Every Rising Step

Optimal

Since there's no limit on how many round trips you can make and no cost per trade, the biggest possible total gain is just the sum of every single day-to-day rise in the price. Any upward run can always be captured by "buying" right before it starts and "selling" right after it ends — and a longer run's total gain equals the sum of its individual daily rises anyway, so there's never a reason to treat a multi-day climb as one trade instead of several back-to-back ones. A single pass comparing each day to the one before it is enough.

TimeO(n)

SpaceO(1)