Find the Maximum Length of a Good Subsequence II

Find the Maximum Length of a Good Subsequence II - Problem

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.

Input & Output

Example 1 — Basic Good Subsequence

$ Input: nums = [1,2,1,1], k = 1

› Output: 4

💡 Note: The entire array [1,2,1,1] forms a good subsequence with exactly 1 transition: 1≠2 at position 0. All other adjacent pairs are equal (2≠1 at position 1 is not counted since we can choose the subsequence [1,1,1,1] by skipping index 1, but the full array gives length 4).

Example 2 — Limited Transitions

$ Input: nums = [1,2,3,4,5], k = 2

› Output: 3

💡 Note: Best subsequence is [1,2,3] with 2 transitions: 1≠2 and 2≠3. We cannot include more elements without exceeding k=2 transitions.

Example 3 — No Transitions Allowed

$ Input: nums = [1,2,1,1,3], k = 0

› Output: 3

💡 Note: With k=0, no adjacent elements can be different. Best subsequence is [1,1,1] with length 3 (all same elements).

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ min(nums.length, 25)

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [1,2,1,1] with k=1 allowed transitions

Count Transitions

Track adjacent differences in potential subsequences

Find Maximum

Return length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Use dynamic programming to track subsequences by ending value and transition count

Asked in

G Google 25 M Meta 18 a Amazon 15 M Microsoft 12

The key insight is to use dynamic programming to track the maximum length of subsequences ending with each value and number of transitions used. The optimal approach uses hash maps to efficiently store states, achieving O(n × k × unique_values) time complexity. Best approach: Hash Map DP with Time: O(n × k × V), Space: O(k × V).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with State Tracking	O(n² × k)	O(n × k)	Use 2D DP to track maximum length ending at each position with limited transitions
Brute Force - Generate All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check if each is good
Optimized DP with Hash Map	O(n × k × unique_values)	O(unique_values × k)	Use hash maps to efficiently track best sequences ending with each value

Dynamic Programming with State Tracking — Algorithm Steps

Step 1: Initialize DP table dp[i][j] for position i with j transitions
Step 2: For each position, try extending sequences from previous positions
Step 3: Update DP values based on whether elements match or differ

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[i][0] = 1 for all positions (single element sequences)

Fill Table

For each position, try extending from previous positions

Track Maximum

Find the maximum value across all dp states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums, int numsSize, int k) {
    if (numsSize == 0) return 0;
    
    // dp[i][j] = max length ending at position i with j transitions used
    int dp[1000][51];
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = -1;
        }
    }
    
    // Base case: single elements use 0 transitions
    for (int i = 0; i < numsSize; i++) {
        dp[i][0] = 1;
    }
    
    int maxLength = 1;
    
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j <= k; j++) {
            // Try extending from all previous positions
            for (int prev = 0; prev < i; prev++) {
                if (nums[prev] == nums[i]) {
                    // Same elements, no additional transition
                    if (dp[prev][j] != -1) {
                        dp[i][j] = max(dp[i][j], dp[prev][j] + 1);
                    }
                } else {
                    // Different elements, need one more transition
                    if (j > 0 && dp[prev][j-1] != -1) {
                        dp[i][j] = max(dp[i][j], dp[prev][j-1] + 1);
                    }
                }
            }
            
            if (dp[i][j] != -1) {
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

For each position i, check all previous positions j, with k transition states

⚠ Quadratic Growth

Space Complexity

O(n × k)

2D DP table storing states for each position and transition count

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

876 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler