0294HardArrayDynamic Programming

Season Flip Limit

Tracked in this browser only

Trains the technique from

LeetCode 188Best Time to Buy and Sell Stock IV

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_flip_total(flips: int, quotes: list[int]) -> int:

Java

public int bestFlipTotal(int flips, int[] quotes)

The intended approach

Time O(n * c) with c = min(flips, n // 2)Space O(c)

Trim the flip cap to n // 2, since no season can fit more closed flips than that. Sweep the days once, keeping for every flip count j the best balance while a copy is in hand and the best balance with nothing in hand. Each day updates the in-hand figure from the previous free figure minus today's price, and the free figure from the in-hand figure plus today's price. The answer is the free figure at the full cap.

Pythonentry point: best_flip_total

def best_flip_total(flips, quotes):
    # More than n // 2 flips can never be used, so the cap is trimmed first.  Two
    # rolling rows are carried: held[j] is the best balance while a copy is in hand
    # having started j flips, free[j] is the best balance with nothing in hand
    # having closed j flips.
    # O(n * c) time and O(c) space with c = min(flips, n // 2).
    n = len(quotes)
    cap = min(flips, n // 2)
    if cap == 0:
        return 0
    neg = float("-inf")
    held = [neg] * (cap + 1)
    free = [0] * (cap + 1)
    for price in quotes:
        for j in range(1, cap + 1):
            if free[j - 1] - price > held[j]:
                held[j] = free[j - 1] - price
            if held[j] + price > free[j]:
                free[j] = held[j] + price
    return free[cap]

The obvious version

Recurse over the days, branching on idle, sell if holding, and buy if a flip remains, and take the best balance reachable from day 0.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_flip_total(flips, quotes):
    n = len(quotes)

    def go(i, holding, left):
        if i == n:
            return 0
        best = go(i + 1, holding, left)
        if holding:
            gain = quotes[i] + go(i + 1, False, left - 1)
            if gain > best:
                best = gain
        elif left > 0:
            gain = -quotes[i] + go(i + 1, True, left)
            if gain > best:
                best = gain
        return best

    return go(0, False, min(flips, n))

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
2 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in