Show problems as
Classic problem #188HardArrayDynamic Programming

Best Time to Buy and Sell Stock IV

Real-world version: Season Flip Limit
Tracked in this browser only
Read Best Time to Buy and Sell Stock IV on LeetCode(opens in a new tab)

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

A reseller works a season of len(quotes) trading days, and quotes[i] is the price a single collectible fetches on day i.

The reseller holds at most one copy at a time. Buying is only allowed with nothing in hand, and selling is only allowed with a copy in hand, so a purchase must be closed by a sale before the next purchase. A buy paired with its sale counts as one flip, and the season allows at most flips of them. Buying and selling on the same day is permitted. Doing nothing on a day is always allowed, and a copy still in hand at the end of the season is simply kept, contributing nothing.

Return the largest total gain the season can produce, where a flip contributes the sale price minus the purchase price. A season with no worthwhile flip returns 0.

Examples

Example 1

Input
flips = 1, quotes = [1,4,2,5]
Output
4

Buy on day 0 at 1 and sell on day 3 at 5. That is one flip and a gain of 4.

Example 2

Input
flips = 2, quotes = [3,8,2,9,1,7]
Output
13

Buy on day 2 at 2 and sell on day 3 at 9 for 7, then buy on day 4 at 1 and sell on day 5 at 7 for 6. Two flips, 13 in total.

Constraints

  • 1 <= flips <= 100
  • 1 <= quotes.length <= 1000
  • 0 <= quotes[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 best_flip_total(flips: int, quotes: list[int]) -> int:
Java
public int bestFlipTotal(int flips, int[] quotes)

More on the same topics