Find the Maximum Length of a Good Subsequence I - Solution & Explanation

Problem Overview: You are given an integer array and an integer k. A subsequence is considered good if the number of times adjacent elements in the subsequence have different values is at most k. The goal is to return the maximum possible length of such a subsequence.

Approach 1: Sliding Window with Counting Changes (O(n) time, O(1) space)

If you treat the problem as finding the longest contiguous segment where the number of adjacent value changes is ≤ k, a two‑pointer sliding window works well. Iterate the array with a right pointer and count how many times nums[i] != nums[i-1]. When this count exceeds k, move the left pointer forward while decreasing the change counter when a transition leaves the window. The window size gives the current candidate length. This approach uses simple iteration and constant memory, making it practical when you interpret the constraint over contiguous elements. Sliding window patterns commonly appear in array problems and help maintain constraints in linear time.

Approach 2: Dynamic Programming with Value Tracking (O(nk) time, O(nk) space)

A more general method treats the problem strictly as a subsequence problem. Maintain dp[j][v], the maximum subsequence length ending with value v using exactly j value changes. When processing a new element x, you either extend a subsequence that already ends with x (no additional change) or transition from a subsequence ending with a different value, which increases the change count. Efficient implementations keep track of the best subsequence length for each j so you can update states in constant time per transition. Hash maps store lengths per value, which connects naturally with hash table techniques.

The key insight: the constraint depends only on whether the next value equals the previous one. Dynamic programming groups subsequences by their last value and the number of changes used so far. Each element updates states from j = k down to 0 to avoid overwriting transitions. This pattern is common in dynamic programming problems where the state depends on the previous element and a limited budget of operations.

Recommended for interviews: The dynamic programming approach is the expected solution because the problem explicitly asks for a subsequence rather than a contiguous segment. Sliding window demonstrates awareness of transition counting, but DP shows stronger algorithmic reasoning and handles the general case with precise state transitions.