Best Time to Buy And Sell Stock II

MEDIUM✓ CHIP-TIMEDLC #122 — FULL STATEMENT ↗

The drill: Maximize total profit from a price series when you can buy and sell as many times as you like, one share at a time, never holding more than one share at once.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A series of daily stock prices arrives, and the task is to walk away with the maximum total profit possible — buying and selling as many separate times as you like.

Only one share can be held at any moment: a share has to be sold before another one is bought, so overlapping holdings are never allowed.

There's no penalty or cost attached to each individual transaction, so chaining together many small trades is exactly as free as making one long one.

EX 01

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

→ 7

TWO SEPARATE RISES: 1→5 AND 3→6

EX 02

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

→ 4

ONE LONG STEADY CLIMB

EX 03

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

→ 0

STRICTLY FALLING, NO PROFIT POSSIBLE

the price series holds up to a few thousand days
prices are non-negative integers, zero included
unlimited transactions are allowed, one share held at a time
no transaction fees or cooldowns apply on this course

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Trying every possible combination of buy and sell days finds the answer, but the number of combinations explodes with every extra day. What does holding a share on day i actually depend on?

HINT 2 THE STRUCTURE

Since a full round trip is always allowed between any two days, ask a smaller question: is tomorrow's price higher than today's? Every such rise is profit you're allowed to bank.

HINT 3 ONE STEP FROM THE ANSWER

Sum up every positive difference between consecutive days — buy the moment before each rise, sell right after it. Chaining every small rise together matches any longer single trade you could have made instead.

COACH'S BOARD — THE PATTERN, STEP BY STEP

BANK EVERY RISEPATTERN · GREEDY, CAPTURE EVERY RISEprices = [7, 1, 5, 3, 6, 4]

RUNNING PROFIT

profit → 0

STEP 1

prices = [7, 1, 5, 3, 6, 4]. Sum every positive day-to-day rise — that equals the max profit with unlimited trades.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/best-time-to-buy-and-sell-stock-ii.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 7 LN

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        def dfs(day: int, holding: bool) -> int:
            if day == n:
                return 0
            skip = dfs(day + 1, holding)
            if holding:
                sell = prices[day] + dfs(day + 1, False)
                return max(skip, sell)
            else:
                buy = -prices[day] + dfs(day + 1, True)
                return max(skip, buy)

        return dfs(0, False)

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 16 LN

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;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int maxProfit(int[] prices) {
        return dfs(prices, 0, false);
    }

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

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED