Show problems as
Classic problem #3177HardArrayHash TableDynamic Programming

Find the Maximum Length of a Good Subsequence II

Real-world version: Longest Pick With Few Changeovers
Tracked in this browser only
Read Find the Maximum Length of a Good Subsequence II on LeetCode(opens in a new tab)

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

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

More on the same topics