Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II is LeetCode 122 (Medium). You get an array prices, where prices[i] is the price of one stock on day i. Return the maximum total profit you can make.
- You may make as many transactions as you like: buy, sell, buy again, sell again.
- You can hold at most one share at any time, so you must sell before you buy again.
- Selling and buying on the same day is allowed, and so is never trading at all, which gives 0.
There are up to 3 × 10⁴ days and each price is at most 10⁴, so the answer has to come from a single linear pass rather than trying every set of trades.
- 1 <= prices.length <= 3 * 10⁴
- 0 <= prices[i] <= 10⁴
Intuition
Draw the prices as a line chart. A trade's profit is the height the line climbs between the buy and the sell, and that climb splits day by day: holding from day a to day b earns exactly the sum of the daily changes in between, rises and falls alike.
With unlimited trades you never have to sit through a fall, because you could have sold the evening before and bought back later. So the most you can collect is every daily rise and none of the falls. Several rising days in a row are not several trades; they add up to the same number as one trade across the whole run.
When a problem allows unlimited non-overlapping transactions with no fee and no cooldown, the answer usually decomposes into independent local gains: add every positive step. The moment a limit appears (one trade, k trades, a fee, a cooldown), the greedy breaks and you need the hold/cash DP instead.
Approach
Before reading on, take [7, 1, 5, 3, 6, 4] and find the best set of trades by hand. Then check whether that total equals the sum of the positive day-to-day differences. Aim for O(n) time and O(1) space.
Two ways to solve it
Add prices[i] - prices[i - 1] whenever it is positive.
- State: one running total.
- Reasoning: every rise is collectable.
- Limits: only fits unlimited, free trades.
The shortest correct answer for LeetCode 122.
Track the best profit holding a share and holding none, and update both each day.
- State: two numbers per day.
- Reasoning: buy, sell or wait, every day.
- Limits: a fee or cooldown is a one-line change.
The version to reach for on follow-ups.
Both are one O(n) pass with O(1) space, and the greedy needs no states at all. The steps, code and live demo below follow the greedy; the DP code comes after the demo.
Start at zero and scan from day 1
Set profit = 0 and loop i from 1 to the last day, comparing each price with the one before it. Starting at 1 means every day has a previous day, and a single-day array simply returns 0 because no trade can finish.
Add each rise, skip each fall
If prices[i] > prices[i - 1], add the difference to profit; otherwise add nothing. A rise is money you earn by holding the share over that day, and a fall or a flat day is a day you would rather not hold it.
Why no schedule beats the sum
Any trade's profit is the sum of the daily changes it covers. Removing the negative ones can only raise that sum, and every positive one is already counted, so no set of trades can earn more than the total of all rises.
Why the sum can actually be traded
Each maximal run of rising days is one real trade: buy at the bottom of the run and sell at its top. The runs never overlap, so you never hold more than one share, and their gains add up to exactly the greedy total.
Best Time to Buy and Sell Stock II solution in Python | C++ | Java
Hold / cash DP
cash is the best profit while holding nothing and hold the best while holding one share. Each day cash may sell at today's price and hold may buy with yesterday's cash; the answer is the final cash.
Common pitfalls
Reusing the one-transaction answer
low = min(low, p) best = max(best, p - low)
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]That is LeetCode 121, which allows a single trade. On [1, 5, 3, 6] it returns 5 (buy at 1, sell at 6), but two trades, 1 to 5 and 3 to 6, make 7.
Adding falling days too
profit += prices[i] - prices[i - 1]
profit += max(0, prices[i] - prices[i - 1])
Without the guard the sum telescopes to prices[-1] − prices[0], the profit of holding from the first day to the last. Skipping the drops is the whole point.
Looping from day 0
for i in range(len(prices)):
... prices[i - 1] ...for i in range(1, len(prices)):
At i = 0, prices[-1] is the last day in Python, so the first comparison silently uses the wrong price. In C++ and Java it reads out of bounds.
Edge cases
The loop from index 1 does not run, so the answer is 0. You cannot buy and sell on different days.
Complexity
Stock II next to its siblings
The best time to buy and sell stock II LeetCode problem is one of five that differ only in the trading rule, and the rule decides whether greedy works.
| Problem | Rule | Method |
|---|---|---|
| 121. Stock I | One transaction | Track the lowest price so far; best sell minus that low. |
| 122. Stock II | Unlimited transactions | Sum every positive daily change. |
| 123. Stock III | At most two transactions | Four-state DP: first buy, first sell, second buy, second sell. |
| 309. With Cooldown | Unlimited, one day rest after selling | Hold/cash DP with a rest state. |
| 714. With Fee | Unlimited, fee per trade | Hold/cash DP, subtract the fee on sell. |
Best Time to Buy and Sell Stock II FAQ
Does the greedy mean buying and selling every day?
No. Consecutive rising days merge into one trade: buy before the run, sell at its end. The daily sum is only a way of computing that total, not a description of the orders you place.
Can the profit overflow an int?
No. The total never exceeds 3 × 10⁴ days × 10⁴, about 3 × 10⁸, so the best time to buy and sell stock II Java and C++ code can keep profit in a 32-bit int. Python integers never overflow.