Get started

Find the Maximum Length of a Good Subsequence I — Medium Problem & Solution

A sequence seq is good if there are at most k indices i in [0, seq.length - 2] with seq[i] != seq[i + 1] — that is, its value changes at most k times from…

Problem statement

A sequence seq is good if there are at most k indices i in [0, seq.length - 2] with seq[i] != seq[i + 1] — that is, its value changes at most k times from one element to the next.

Return the maximum possible length of a good subsequence of nums (delete any elements, keep the rest in order).

Example 1

Input: nums = [1,2,1,1,3], k = 2
Output: 4
Explanation: `[1,2,1,1]` changes value twice.

Example 2

Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation: `[1,1]` — no changes allowed.

Example 3

Input: nums = [4,4,9,4], k = 1
Output: 3

Constraints

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(nums.length, 25)

How to solve Find the Maximum Length of a Good Subsequence I

Let f[v][j] be the longest good subsequence (at most j changes) that ends with value v, and best[j] = max over v of f[v][j]. Appending nums[i] = v either continues a subsequence ending in v (no new change) or follows a subsequence ending in anything else (one more change).

Approach

  1. Process nums left to right. For the current value v, for j from k down to 0:
  2. f[v][j] = 1 + max(f[v][j], j > 0 ? best[j - 1] : 0) — the old f[v][j] continues a run of v, best[j - 1] pays one change.
  3. Update best[j] = max(best[j], f[v][j]).
  4. Return best[k].

Why it works

Going through j downwards means best[j - 1] still describes elements before the current one when it is read. best[j - 1] may itself end in v, which would not actually need a change — but then f[v][j] >= f[v][j - 1] already gives at least as much, so the overcount never wins. Every good subsequence ending at the current element is one of the two cases, so the values are exact.

Complexity

  • Time — O(n · k)
  • Space — O(d · k) for d distinct values

Pitfalls

  • Count changes between neighbours of the subsequence, not of the original array.
  • Iterate j downwards, or the current element can be used twice.
  • With k = 0 the answer is the highest frequency of any value.

Reference solution

Python

from typing import List

def maximumLength(nums: List[int], k: int) -> int:
    best = [0] * (k + 1)
    f = {}
    for v in nums:
        cur = f.get(v)
        if cur is None:
            cur = [0] * (k + 1)
            f[v] = cur
        for j in range(k, -1, -1):
            cand = cur[j] + 1
            if j > 0 and best[j - 1] + 1 > cand:
                cand = best[j - 1] + 1
            cur[j] = cand
            if cand > best[j]:
                best[j] = cand
    return best[k]

JavaScript

var maximumLength = function(nums, k) {
    var best = new Array(k + 1).fill(0);
    var f = new Map();
    for (var i = 0; i < nums.length; i++) {
        var v = nums[i];
        var cur = f.get(v);
        if (cur === undefined) {
            cur = new Array(k + 1).fill(0);
            f.set(v, cur);
        }
        for (var j = k; j >= 0; j--) {
            var cand = cur[j] + 1;
            if (j > 0 && best[j - 1] + 1 > cand) cand = best[j - 1] + 1;
            cur[j] = cand;
            if (cand > best[j]) best[j] = cand;
        }
    }
    return best[k];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming