Show problems as
Classic problem #309MediumArrayDynamic Programming

Best Time to Buy and Sell Stock with Cooldown

Real-world version: Reselling One Lot With a Rest Day
Tracked in this browser only
Read Best Time to Buy and Sell Stock with Cooldown on LeetCode(opens in a new tab)

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

A reseller watches one component whose quoted price on day i is prices[i].

The rules of the desk are:

  • At most one lot may be held at any moment, so a lot has to be sold before another is bought.
  • A lot bought on some day may be sold on that day or on any later day.
  • The day straight after a sale is a rest day: no buying is allowed on it. If a sale happens on day i, the earliest possible next purchase is day i + 2.
  • Buying and selling may be repeated as often as the rules allow, and it is always allowed to trade nothing at all.

Return the largest profit the reseller can finish with.

Examples

Example 1

Input
prices = [5, 10, 1, 10]
Output
9

Buying on day 2 at 1 and selling on day 3 at 10 gains 9. Buying on day 0 at 5 and selling on day 1 at 10 gains 5, and day 2 is then a rest day, so day 3 is the only day left to buy on and there is no later day to sell on.

Example 2

Input
prices = [9, 8, 7, 6, 5]
Output
0

Every later quote is below every earlier one, so any completed trade loses money and trading nothing is allowed.

Example 3

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

Buying on day 1 at 1 and selling on day 2 at 3 gains 2, day 3 is the rest day, and buying on day 4 at 4 then selling on day 5 at 7 gains 3, for 5 in total.

Constraints

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

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 max_profit(prices: list[int]) -> int:
Java
public int maxProfit(int[] prices)

More on the same topics