1187MediumArrayDynamic Programming

Picking Parcels with Steady Totals

Tracked in this browser only

Trains the technique from

LeetCode 3201Find the Maximum Length of Valid Subsequence I

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 conveyor carries parcels past you, loads[i] being the weight of the i-th.

Pick out some of the parcels, keeping the order they came in. Add up each neighbouring pair of the parcels you picked: the first with the second, the second with the third, and so on. Your pick counts as steady when those totals are all even or all odd.

Return the largest number of parcels a steady pick can hold. A pick of one or two parcels is always steady, since there is no second total to disagree with the first.

Examples

Example 1

Input: loads = [7, 2, 9, 4, 1, 6, 3]
Output: 7

The weights already run odd, even, odd, even down the conveyor, so every neighbouring total is odd and the whole run is steady on its own.

Example 2

Input: loads = [1, 2, 3, 3, 4]
Output: 4

Dropping the second parcel of weight 3 leaves weights 1, 2, 3 and 4, whose totals 3, 5 and 7 are all odd. Keeping all five would stand the two 3s side by side for an even total.

Example 3

Input: loads = [6, 6, 1, 6, 6, 1, 6, 6]
Output: 6

Taking the six parcels of weight 6 makes every neighbouring total 12, all even. Alternating instead would have to stop at five parcels, since only two odd weights are on offer.

Constraints

2 <= loads.length <= 2 * 10^5
1 <= loads[i] <= 10^7

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(loads: list[int]) -> int:

Java

public int maximumLength(int[] loads)

The intended approach

Time O(n) over the conveyor.Space O(1) beyond the input.

Only the parity of each weight matters, since the parity of a pair's total is decided by the parities of the two weights. There are just two kinds of steady pick. Every total even means the two weights of each neighbouring pair share a parity, so the whole pick shares one parity. The best such pick takes every odd parcel or every even parcel, whichever kind is more common, so it is simply the larger of the two counts. Every total odd means each neighbouring pair mixes an odd weight with an even one, so the parities along the pick alternate. Building the longest alternating pick is greedy: fix the parity you want first, walk the conveyor, take a parcel whenever its parity is the one you are waiting for, and flip what you are waiting for. Taking the earliest parcel of the wanted parity never costs anything, because a later one of that parity leaves fewer parcels behind for the rest of the pick. Run that from each of the two starting parities and keep the longer result. The answer is the best of those, and with at least two parcels on the conveyor it is at least two: any two parcels form a steady pick on their own.

Pythonentry point: maximum_length

def maximum_length(loads):
    odd = 0
    for load in loads:
        odd += load & 1
    best = max(odd, len(loads) - odd)
    for start in (0, 1):
        want = start
        taken = 0
        for load in loads:
            if load & 1 == want:
                taken += 1
                want ^= 1
        if taken > best:
            best = taken
    return best

The obvious version

Fill a table instead. For each of the two possible parities of the totals, let `best[i]` be the longest steady pick that ends on parcel `i` and whose totals all have that parity. A pick ending at `i` either stops there alone or extends some pick ending at an earlier parcel `j` whose weight makes the wanted parity with parcel `i`, so scan every earlier `j` for each `i`. The answer is the largest entry over both parities. Costs a scan per parcel.

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(loads):
    n = len(loads)
    answer = 1
    for parity in (0, 1):
        best = [1] * n
        for i in range(n):
            for j in range(i):
                if (loads[j] + loads[i]) % 2 == parity and best[j] + 1 > best[i]:
                    best[i] = best[j] + 1
            if best[i] > answer:
                answer = best[i]
    return answer

How this problem was checked

Reference solution executed against 14 test cases — 14 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