0911HardArrayHash TableDynamic Programming

Longest Pick With Few Changeovers

Tracked in this browser only

Trains the technique from

LeetCode 3177Find the Maximum Length of a Good Subsequence II

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.

Readings are given as nums. A pick takes some of them, keeping their order. A changeover is a place in the pick where a reading differs from the one directly before it.

Return the greatest number of readings a pick can hold while making at most k changeovers.

Examples

Example 1

Input: nums = [7, 2, 7, 2, 9, 2, 7], k = 2
Output: 5

Picking 7, 7, 2, 2 uses one changeover and holds four readings; picking 7, 2, 2, 2 also holds four. Taking a fifth reading would need a third changeover.

Example 2

Input: nums = [1, 2, 3, 4, 5], k = 0
Output: 1

Every reading differs from every other, so with no changeovers allowed a pick can hold only one.

Example 3

Input: nums = [4, 4, 4, 4, 4], k = 0
Output: 5

All the readings match, so the whole list is one pick with no changeovers.

Constraints

1 <= nums.length <= 5000
1 <= nums[i] <= 10^9
0 <= k <= 50
k is at most nums.length

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 maximum_length(nums: list[int], k: int) -> int:

Java

public int maximumLength(int[] nums, int k)

The intended approach

Time O(n * k) for n readings and a budget of k.Space O(n * k) for the per-value records across the budgets.

Sweep the readings once, holding for every changeover budget the best pick built so far, split two ways: the best pick ending in each particular reading, and the best pick ending in anything at all. Those two are what a new reading needs. Taking the new reading onto a pick that already ends in that same value adds no changeover, so it extends the first record. Taking it onto a pick ending in anything else costs one changeover, so it extends the second record from one budget lower. Both records are updated for every budget as the reading is read, walking the budgets downwards so each one still sees the previous reading's figures rather than this one's. Keying the per-value record by value in a table keeps the work proportional to the budget rather than to the number of distinct readings.

Pythonentry point: maximum_length

def maximum_length(nums, k):
    ending = [dict() for _ in range(k + 1)]   # best pick ending in a given value
    best = [0] * (k + 1)                      # best pick ending in anything
    for v in nums:
        for j in range(k, -1, -1):
            run = ending[j].get(v, 0) + 1
            if j > 0 and best[j - 1] + 1 > run:
                run = best[j - 1] + 1
            if run > ending[j].get(v, 0):
                ending[j][v] = run
            if run > best[j]:
                best[j] = run
    return best[k]

The obvious version

Try every pick there is by deciding for each reading whether to take it, count the changeovers in the ones that qualify, and keep the longest. Exponential in the reading count and it keeps no records at all.

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_maximum_length(nums, k):
    n = len(nums)
    best = 0
    for mask in range(1 << n):
        picked = []
        for i in range(n):
            if mask >> i & 1:
                picked.append(nums[i])
        changeovers = 0
        for i in range(1, len(picked)):
            if picked[i] != picked[i - 1]:
                changeovers += 1
        if changeovers <= k and len(picked) > best:
            best = len(picked)
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 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