Show problems as
Classic problem #123HardArrayDynamic Programming

Best Time to Buy and Sell Stock III

Real-world version: Two Resale Rounds on the Scrap Board
Tracked in this browser only
Read Best Time to Buy and Sell Stock III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A scrap dealer posts one price per day for a pallet of recycled aluminium, and trades in either direction at that price. quotes[i] is the posted price on day i.

You may own at most one pallet at any moment, and a pallet you buy has to be sold on a strictly later day. A round is one purchase followed by its sale, and you may complete at most two rounds; the day a pallet is sold may also be the day the next one is bought.

Return the largest profit these rounds can add up to. Sitting the whole stretch out is allowed, so the answer is never below 0.

Examples

Example 1

Input
quotes = [12, 5, 9, 3, 11, 4, 10]
Output
14

Buy on day 3 at 3 and sell on day 4 at 11 for 8, then buy on day 5 at 4 and sell on day 6 at 10 for 6. The two rounds add up to 14.

Example 2

Input
quotes = [9, 8, 7, 6]
Output
0

Every later day posts a lower price than every earlier one, so no purchase can be sold for more than it cost and no round is opened.

Example 3

Input
quotes = [4, 6]
Output
2

Buy on day 0 at 4 and sell on day 1 at 6 for 2. Only one round fits in two days, and using fewer than two rounds is allowed.

Constraints

  • 1 <= quotes.length <= 10^5
  • 0 <= quotes[i] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_two_rounds(quotes: list[int]) -> int:
Java
public int bestTwoRounds(int[] quotes)

More on the same topics