LeetCode: 122. Best Time to Buy and Sell Stock II

2026-03-21

Use two DP states, `cash` and `hold`, to track the maximum profit in O(N) time.

LeetCode: 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

Summary

You are given an integer array prices where prices[i] is the price of a stock on the i-th day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Approach

Use dynamic programming.

There are two possible states for the trader:

  1. not holding a stock: only cash
  2. holding a stock: cash minus the stock price

Each day, the trader decides what to do based on the previous state. We need to track the maximum profit for both states, not just whether we are holding a stock.

So we keep two state values:

  • cash[i]: the maximum profit at the end of day i when we are not holding a stock
  • hold[i]: the maximum profit at the end of day i when we are holding a stock

Cash:

There are two cases for updating cash:

  • keep not holding a stock: use the previous cash
  • sell the stock today: use previous hold + price
cash = max(previous cash, previous hold + price)

Hold:

There are two cases for updating hold:

  • keep holding the current stock
  • buy a new stock today if we were not holding one
hold = max(previous hold, previous cash - price)

At the end, the answer is cash, because the maximum realized profit must be in the state where we are not holding a stock.

Function

Initialize:

  • cash = 0
  • hold = -prices[0]

For each price in prices after the first one:

  • cash = max(previous cash, previous hold + price)
  • hold = max(previous hold, previous cash - price)

Return cash.

Complexity

Time complexity: O(N) Space complexity: O(1)