Find the Maximum Length of a Good Subsequence II

Hard
1656.

Find the Maximum Length of a Good Subsequence II

Find the Maximum Length of a Good Subsequence II is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

You are given an integer array nums and a non-negative integer k.

A sequence seq is good if at most k indices i in the range [0, seq.length - 2] satisfy seq[i] != seq[i + 1] — that is, its value changes between neighbours at most k times.

Return the maximum possible length of a good subsequence of nums.

Example 1

Input
nums = [1,2,1,1,3], k = 2
Output
4
Explanation
[1,2,1,1] changes value twice (1→2, 2→1).

Example 2

Input
nums = [1,2,3,4,5,1], k = 0
Output
2
Explanation
With no changes allowed, take equal values only: the two 1s.

Example 3

Input
nums = [7], k = 0
Output
1

Constraints

  • 1 <= nums.length <= 5 * 10^3
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(50, nums.length)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumLength = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Maximum Length of a Good Subsequence II — Solution

Find the Maximum Length of a Good Subsequence II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Maximum Length of a Good Subsequence II is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

Problem statement

You are given an integer array nums and a non-negative integer k.

A sequence seq is good if at most k indices i in the range [0, seq.length - 2] satisfy seq[i] != seq[i + 1] — that is, its value changes between neighbours at most k times.

Return the maximum possible length of a good subsequence of nums.

Example 1

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

Example 2

Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation: With no changes allowed, take equal values only: the two 1s.

Example 3

Input: nums = [7], k = 0
Output: 1

Constraints

  • 1 <= nums.length <= 5 * 10^3
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(50, nums.length)

Hints for Find the Maximum Length of a Good Subsequence II

  1. Hint 1

    Let dp[x][j] be the longest good subsequence (so far) that ends with value x and uses at most j changes.

  2. Hint 2

    When you read another x, it can extend a subsequence already ending in x for free, or follow the best subsequence of any value that used at most j - 1 changes.

  3. Hint 3

    Keep best[j] = max over all values of dp[·][j]. Process j from k down to 0 so best[j - 1] still describes earlier elements: dp[x][j] = max(dp[x][j], best[j - 1]) + 1, then raise best[j].

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

A DP over (last value, changes used) is natural but naively takes O(n^2 k). The trick: the best predecessor with a different value only matters through its length, so a running maximum best[j] over all values replaces the inner loop.

Approach

  1. Map each distinct value to an index and keep dp[value][0..k] (initially 0) and best[0..k].
  2. For each element x, for j from k down to 0: dp[x][j] = max(dp[x][j], j > 0 ? best[j - 1] : 0) + 1, then best[j] = max(best[j], dp[x][j]).
  3. Return the maximum of best.

Why it works

A good subsequence ending at this x with at most j changes either had x before it (same value, no new change — the old dp[x][j]), or had some other value before it, spending one change on top of a subsequence with at most j - 1 changes. Using best[j - 1] also allows a predecessor ending in x; counting that as a change only overestimates the changes used, so the result is still a valid subsequence and never exceeds the true optimum. Going from k down keeps this element from being used twice.

Complexity

  • Time — O(n · k)
  • Space — O(n · k)

Pitfalls

  • Updating j upwards lets one element follow itself through best[j - 1] in the same step.
  • Values reach 10^9 — index them with a hash map, not an array.
  • With k = 0 the answer is the largest frequency of a single value.

Reference solution

Python

from typing import List

def maximumLength(nums: List[int], k: int) -> int:
    dp = {}
    best = [0] * (k + 1)
    for x in nums:
        row = dp.get(x)
        if row is None:
            row = [0] * (k + 1)
            dp[x] = row
        for j in range(k, -1, -1):
            prev = best[j - 1] if j > 0 else 0
            row[j] = max(row[j], prev) + 1
            if row[j] > best[j]:
                best[j] = row[j]
    return max(best)

Java

public static int maximumLength(int[] nums, int k) {
    HashMap<Integer, int[]> dp = new HashMap<>();
    int[] best = new int[k + 1];
    for (int x : nums) {
        int[] row = dp.computeIfAbsent(x, key -> new int[k + 1]);
        for (int j = k; j >= 0; j--) {
            int prev = j > 0 ? best[j - 1] : 0;
            row[j] = Math.max(row[j], prev) + 1;
            best[j] = Math.max(best[j], row[j]);
        }
    }
    int ans = 0;
    for (int v : best) ans = Math.max(ans, v);
    return ans;
}

C++

int maximumLength(vector<int>& nums, int k) {
    unordered_map<int, vector<int>> dp;
    vector<int> best(k + 1, 0);
    for (int x : nums) {
        auto it = dp.find(x);
        if (it == dp.end()) it = dp.emplace(x, vector<int>(k + 1, 0)).first;
        vector<int>& row = it->second;
        for (int j = k; j >= 0; j--) {
            int prev = j > 0 ? best[j - 1] : 0;
            row[j] = max(row[j], prev) + 1;
            best[j] = max(best[j], row[j]);
        }
    }
    return *max_element(best.begin(), best.end());
}

JavaScript

var maximumLength = function(nums, k) {
    var dp = new Map();
    var best = new Array(k + 1).fill(0);
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        var row = dp.get(x);
        if (row === undefined) { row = new Array(k + 1).fill(0); dp.set(x, row); }
        for (var j = k; j >= 0; j--) {
            var prev = j > 0 ? best[j - 1] : 0;
            row[j] = Math.max(row[j], prev) + 1;
            if (row[j] > best[j]) best[j] = row[j];
        }
    }
    return Math.max.apply(null, best);
};

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

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets