Skip to content

122. Best Time to Buy and Sell Stock II

On LeetCode ->

Reformulated question

Given daily stock prices, you may buy and sell any number of times, but can hold at most one share at once.

Return the maximum total profit.

Compact example:

prices = [1, 5, 3, 6]
best = (buy 1 -> sell 5) + (buy 3 -> sell 6)
output = 7

Key trick

Every upward step can be taken independently.

  • Add prices[i] - prices[i - 1] whenever it is positive.
  • This is equivalent to buying before each rise and selling after it.

Trap

Common mistakes:

  • Solving it like Stock I and keeping only one transaction.
  • Overcomplicating with valley/peak state machines.
  • Forgetting profit is 0 for decreasing or single-element arrays.
  • Thinking you must hold until the local maximum explicitly, while summing all positive day-to-day gains gives the same result.

Why this question is interesting

It looks like a trading simulation, but the real idea is a greedy decomposition.

  • A long rise:
  • [1, 2, 3, 4]
  • Is the same profit as:
  • (2 - 1) + (3 - 2) + (4 - 3) = 4 - 1

Pytest test

import pytest

@pytest.mark.parametrize(
    ("prices", "expected"),
    [
        ([7, 1, 5, 3, 6, 4], 7),
        ([1, 2, 3, 4, 5], 4),
        ([7, 6, 4, 3, 1], 0),
        ([5], 0),
        ([2, 2, 2], 0),
        ([1, 3, 2, 4, 1, 5], 8),
        ([3, 2, 6, 5, 0, 3], 7),
        ([1, 2, 1, 2, 1, 2], 3),
    ],
)
def test_max_profit(prices, expected):
    assert Solution().maxProfit(prices) == expected

Solve the problem with idiomatic Python

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # Sum every positive increase between consecutive days.
        profit = 0

        for i in range(1, len(prices)):
            gain = prices[i] - prices[i - 1]
            if gain > 0:
                profit += gain

        return profit

Library version with same idea:

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        return sum(
            max(0, prices[i] - prices[i - 1])
            for i in range(1, len(prices))
        )

Comment my solution

Your solution works on typical cases, but it is harder than needed.

  • Good:
  • It correctly tries to merge descending scans into transactions.
  • Problems:
  • Reverse traversal with buy and sell state is much less obvious.
  • It is harder to prove correct than the greedy positive-deltas solution.
  • Interviewers usually expect the simple greedy observation, not a custom state machine.

The simpler invariant is:

  • Every profitable rise from one day to the next should be taken.
  • So just sum all positive adjacent differences.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # assume prices not None
        sell = prices[len(prices) - 1]
        buy = None
        profit = 0

        for i in range(len(prices) - 2, -1, -1):
            if buy is None:
                if prices[i] > sell:
                    sell = prices[i]
                else:
                    buy = prices[i]
                continue
            if prices[i] > buy:
                profit += sell - buy
                sell = prices[i]
                buy = None
                continue
            else:
                buy = prices[i]

        if buy is not None:
            profit += sell - buy

        return profit

class Solution:
    # After reading AI comment on my solution
    def maxProfit(self, prices: list[int]) -> int:
        profit = 0
        for today, tomorrow in zip(prices, prices[1:]):
            delta = tomorrow - today
            if delta > 0:
                profit += delta
        return profit

## Test

import pytest

@pytest.mark.parametrize(
    ("prices", "profit"),
    [([7,1,5,3,6,4], 7), ([1,2,3,4,5], 4), ([7,6,4,3,1], 0)]
)
def test_best_time_to_buy_and_sell_stock_ii(prices, profit):
    assert Solution().maxProfit(prices) == profit

Code

import pytest


# Reformulated example:
# prices = [1, 5, 3, 6]
# transactions: (1 -> 5) + (3 -> 6)
# expected profit = 7


class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # Greedy:
        # if price goes up from yesterday to today, take that gain.
        profit = 0
        for i in range(1, len(prices)):
            gain = prices[i] - prices[i - 1]
            if gain > 0:
                profit += gain
        return profit


class SolutionOneLiner:
    def maxProfit(self, prices: list[int]) -> int:
        # Same idea, compact form.
        return sum(
            max(0, prices[i] - prices[i - 1])
            for i in range(1, len(prices))
        )


@pytest.mark.parametrize(
    ("prices", "expected"),
    [
        ([7, 1, 5, 3, 6, 4], 7),
        ([1, 2, 3, 4, 5], 4),
        ([7, 6, 4, 3, 1], 0),
        ([5], 0),
        ([2, 2, 2], 0),
        ([1, 3, 2, 4, 1, 5], 8),
        ([3, 2, 6, 5, 0, 3], 7),
        ([1, 2, 1, 2, 1, 2], 3),
    ],
)
def test_max_profit(prices, expected):
    assert Solution().maxProfit(prices) == expected
    assert SolutionOneLiner().maxProfit(prices) == expected


Solution().maxProfit([7, 1, 5, 3, 6, 4])  # 7
Solution().maxProfit([1, 2, 3, 4, 5])     # 4
Solution().maxProfit([7, 6, 4, 3, 1])     # 0