We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Length of a Good Subsequence I

Number: 3456

Difficulty: Medium

Paid? No

Companies: Snowflake

Problem Description

Given an integer array nums and a non-negative integer k, find the maximum length of a subsequence of nums (not necessarily contiguous) that is "good". A subsequence is defined as good if there are at most k indices i (in the subsequence’s order) for which the adjacent elements differ (i.e. seq[i] != seq[i+1]). In other words, you may switch between different numbers at most k times while building the subsequence.

Key Insights

  • We can pick elements non-contiguously; only the relative order matters.
  • The “good” subsequence allows at most k transitions between different consecutive values.
  • When adding an element equal to the previous one, no new transition is introduced.
  • When adding a different element, we “spend” one of the allowed k changes.
  • Dynamic programming with memoization can efficiently explore decisions at each index.

Space and Time Complexity

Time Complexity: O(n * (k+1) * U) where n is the length of nums and U is the number of unique states for the last picked value (at most n distinct numbers)
Space Complexity: O(n * (k+1) * U) due to the memoization cache and recursion call stack

Solution

We use a recursive dynamic programming approach with memoization. The state is defined by: • i: the current index in nums being considered
• last: the last number included in our subsequence (or a sentinel value if none has been picked)
• rem: the remaining allowed transitions (initially equal to k)

At each step:

  1. We decide to skip nums[i] and move on.
  2. Or we decide to take nums[i]:
    • If no element has been picked (last is undefined) or nums[i] equals the last picked element, then no extra transition is used.
    • If nums[i] is different from last and we have at least one allowed transition rem > 0, we take it and decrement rem.
  3. We choose the option that maximizes the length of the subsequence.

By memoizing each state (i, last, rem), we ensure that every unique subproblem is computed only once.

Code Solutions

# Python solution using recursion with memoization
def maxGoodSubsequence(nums, k):
    from functools import lru_cache
    n = len(nums)
    
    # Using None as a sentinel for "no last element"
    @lru_cache(maxsize=None)
    def dp(i, last, rem):
        # Base condition: if we've considered all elements
        if i == n:
            return 0
        
        # Option 1: Skip the current element
        skip = dp(i + 1, last, rem)
        
        # Option 2: Take the current element if allowed
        take = 0
        current = nums[i]
        if last is None or current == last:
            # Taking the element without a change penalty
            take = 1 + dp(i + 1, current, rem)
        elif rem > 0:
            # Taking the element and using one transition
            take = 1 + dp(i + 1, current, rem - 1)
        
        # Return the best of taking or skipping
        return max(skip, take)
    
    return dp(0, None, k)

# Example usage:
print(maxGoodSubsequence([1,2,1,1,3], 2))  # Expected output: 4
print(maxGoodSubsequence([1,2,3,4,5,1], 0))  # Expected output: 2
← Back to All Questions