Show problems as
Classic problem #3201MediumArrayDynamic Programming

Find the Maximum Length of Valid Subsequence I

Real-world version: Picking Parcels with Steady Totals
Tracked in this browser only
Read Find the Maximum Length of Valid Subsequence I on LeetCode(opens in a new tab)

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

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

Python
def maximum_length(loads: list[int]) -> int:
Java
public int maximumLength(int[] loads)

More on the same topics