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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^31 <= nums[i] <= 10^90 <= k <= min(50, nums.length)
Hints for Find the Maximum Length of a Good Subsequence II
Hint 1
Let
dp[x][j]be the longest good subsequence (so far) that ends with valuexand uses at mostjchanges.Hint 2
When you read another
x, it can extend a subsequence already ending inxfor free, or follow the best subsequence of any value that used at mostj - 1changes.Hint 3
Keep
best[j]= max over all values ofdp[·][j]. Processjfromkdown to 0 sobest[j - 1]still describes earlier elements:dp[x][j] = max(dp[x][j], best[j - 1]) + 1, then raisebest[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
- Map each distinct value to an index and keep
dp[value][0..k](initially 0) andbest[0..k]. - For each element
x, forjfromkdown to 0:dp[x][j] = max(dp[x][j], j > 0 ? best[j - 1] : 0) + 1, thenbest[j] = max(best[j], dp[x][j]). - 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
jupwards lets one element follow itself throughbest[j - 1]in the same step. - Values reach
10^9— index them with a hash map, not an array. - With
k = 0the 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