You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].
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:
The maximum length subsequence is [1,2,1,1,3].
Example 2:
Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation:
The maximum length subsequence is [1,2,3,4,5,1].
Constraints:
1 <= nums.length <= 5001 <= nums[i] <= 1090 <= k <= min(nums.length, 25)To solve #3176 Find the Maximum Length of a Good Subsequence I, we need to construct a subsequence while controlling how many times adjacent elements in the subsequence differ. This naturally leads to a dynamic programming strategy combined with efficient lookups using a hash table.
The key idea is to track the longest subsequence ending with a particular value while allowing up to k transitions where consecutive elements differ. For each number in the array, we update DP states that represent the maximum length achievable with a certain number of allowed changes. A hash map helps quickly retrieve the best subsequence length ending with the same value, while additional states track sequences that involve switching to a different value.
By iterating through the array and updating these DP states carefully, we build the best possible subsequence length under the given constraint. This approach avoids brute-force subsequence generation and keeps the computation efficient.
The optimized solution typically runs in O(n × k) time with O(k × distinct values) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Hash Map | O(n × k) | O(k × distinct values) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
The absolute values in <code>nums</code> don’t really matter. So we can remap the set of values to the range <code>[0, n - 1]</code>.
Let <code>dp[i][j]</code> be the length of the longest subsequence till index <code>j</code> with at most <code>i</code> positions such that <code>seq[i] != seq[i + 1]</code>.
For each value <code>x</code> from left to right, update <code>dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1)</code>, where <code>y != x</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Dynamic programming works well because the decision at each element depends on previously computed subsequences. By storing the best results for each state, we avoid recomputation and can extend valid subsequences efficiently.
Problems involving subsequences with constraints are common in coding interviews. Variants using dynamic programming and hash maps are frequently asked at top tech companies to test optimization and state transition reasoning.
A hash table is very useful for quickly storing and retrieving the best subsequence length for each value. When combined with dynamic programming states that track allowed transitions, it helps update results efficiently as you iterate through the array.
The optimal approach uses dynamic programming combined with hash maps. It tracks the best subsequence length ending with each value while allowing up to k changes between adjacent elements. This avoids brute-force subsequence enumeration and keeps the runtime manageable.