← DSA Atlas
Dedicated problem page · #122

Best Time to Buy and Sell Stock II

MediumStock and State-Machine DPGreedy on consecutive gainsState-machine DP (hold vs cash)
Solve on LeetCode ↗
122
MediumStock and State-Machine DPState-machine DP (hold vs cash)Greedy on consecutive gains

Best Time to Buy and Sell Stock II

Given an array prices where prices[i] is the price of a stock on day i, you may complete as many transactions as you like (buy one and sell one share, repeatedly), but you can hold at most one share at a time and must sell before buying again. Return the maximum profit you can achieve.

Open official problem prompt ↗
In plain English

Find the largest total profit when you can trade repeatedly but hold at most one share at a time.

Picture it like this

Like a hiker who earns money for every uphill meter climbed and loses nothing on descents: the smart move is to bank every single climb, no matter how many hills there are.

Example
Input
prices = [7, 1, 5, 3, 6, 4]
Output
7
Why
Buy at 1 sell at 5 (+4), then buy at 3 sell at 6 (+3); total 7.
Constraints
1 <= prices.length <= 3 * 10^40 <= prices[i] <= 10^4
Pattern lesson

See the pattern, then code

Greedy on consecutive gains
Recognition clue

Unlimited transactions with only one share held at a time and no cooldown or fee is the signal that every upward step can be captured independently.

↗
Stock and State-Machine DP

A small set of modes such as holding, free, cooldown, or transactions left.. Because there is no limit on the number of trades and no fee, any multi-day rise can be decomposed into a chain of consecutive up-moves, so summing every positive day-to-day difference equals the best possible profit.

New words, made simpleKnow these before the algorithm
Transaction
One buy followed by one later sell of a single share.
Consecutive gain
A positive difference between adjacent days, prices[i] - prices[i-1].
Greedy
Making the locally optimal choice (grab every rise) that happens to be globally optimal here.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Peak-valley scan

Correct but needs more bookkeeping than necessary.

Find each local valley then the next local peak and add peak minus valley.

Time O(n)Space O(1)
Best choiceSum of positive differences

Simplest correct form; buying at a valley and selling at a peak equals summing all the up-steps between them.

Add prices[i] - prices[i-1] whenever it is positive.

Time O(n)Space O(1)
The rule we keep true

Invariant

After processing day i, profit equals the maximum achievable using only prices[0..i].

Why this is correct

Reasoning

A profitable buy-low/sell-high span telescopes: (p[j]-p[i]) equals the sum of consecutive differences from i to j, and any negative difference in that span would only lower the total, so keeping just the positive steps is optimal and never over-counts because you never hold more than one share.

The algorithm in three movesSay these aloud before coding
1Walk the prices from the second day onward

1->5 rise: profit += 4

2Whenever today's price exceeds yesterday's, add the difference to the profit

3->6 rise: profit += 3

3Ignore days where the price falls or stays flat

profit = 7

4Return the accumulated profit

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
70
11
52
33
64
45
1 · Readprice 1 vs 7
2 · AskDid the price rise?
3 · Update stateprofit = 0
4 · ResultFell, skip.
Key takeaway

Every rising segment (1->5 and 3->6) is collected; falling segments are skipped.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Initialize profit

    Start with zero accumulated profit.

  2. 2
    Lines 4-6Collect rises

    For each day, add the gain over the previous day only when it is positive.

  3. 3
    Lines 7Return

    The sum of all positive steps is the maximum profit.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Strictly decreasing prices yield profit 0 (never trade)
  • Single-day array returns 0
  • Flat runs of equal prices contribute nothing
!

Common beginner mistakes

  • Trying to find one global buy/sell pair (that solves problem 121, not this one)
  • Attempting to hold multiple shares to stack gains, which the one-share rule forbids
  • Adding negative differences and dragging the total down
Check your understanding

Why does summing every positive daily difference never violate the one-share-at-a-time rule?

More in Stock and State-Machine DP

#123Best Time to Buy and Sell Stock IIIFour-state transaction machine#188Best Time to Buy and Sell Stock IVk-transaction state machine#714...with Transaction FeeCash/hold state machine with per-sale fee