Skip to main content

122. Best Time to Buy and Sell Stock II

medium

Maximize profit with unlimited buy/sell transactions, holding at most one share at a time. The state-machine DP (hold / cash) introduces a recurring tool kit for the entire stock-trading DP family.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.

Constraints

  • 1 <= prices.length <= 3 * 10^4
  • 0 <= prices[i] <= 10^4

Examples

Example 1

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

Explanation: Buy day 2 (price=1), sell day 3 (price=5), profit = 4. Buy day 4 (3), sell day 5 (6), profit = 3. Total = 7.

Example 2

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

Example 3

Input
prices = [7,6,4,3,1]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two-state DP: cash[i] = max profit on day i holding nothing; hold[i] = max profit on day i holding a share.

Hint 2

Transitions: cash[i] = max(cash[i-1], hold[i-1] + prices[i]); hold[i] = max(hold[i-1], cash[i-1] - prices[i]).

Hint 3

Greedy shortcut: sum every positive consecutive difference. Same answer, O(1) extra space.

Solution approach

Reveal approach

Two-state DP. Define cash[i] = maximum profit at end of day i holding 0 shares; hold[i] = maximum profit at end of day i holding 1 share. The recurrence relations are cash[i] = max(cash[i-1], hold[i-1] + prices[i]) — either keep no shares or sell today — and hold[i] = max(hold[i-1], cash[i-1] - prices[i]) — either keep the share or buy today. Base cases cash[0] = 0, hold[0] = -prices[0]. The answer is cash[n-1] since you must end with no share to bank profit. Drop the arrays for two rolling variables for O(1) extra space. A cleaner equivalent: since you can buy and sell as many times as you want, the optimal profit equals the sum of all positive (prices[i] - prices[i-1]). Both views give O(n) time.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • state-machine-dp
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Best Time to Buy and Sell Stock II and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →