Skip to content

122. Best Time to Buy and Sell Stock II

On LeetCode ->

Problem

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.

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 is it 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

Python solution

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

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

        return profit

    def maxProfit_2(self, prices: list[int]) -> int:
        n = len(prices)
        return sum(
            max(0, prices[i] - prices[i - 1])
            for i in range(1, n)
        )

Comment on 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