LeetCode 3176 - Find the Maximum Length of a Good Subsequence I

LeetCode Problem 3176

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

We are given an integer array nums and a non-negative integer k. We need to find the maximum possible length of a subsequence such that the number of adjacent unequal pairs is at most k.

A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements. The elements do not need to be contiguous.

The condition for a subsequence to be "good" is based on transitions between neighboring elements inside the subsequence. For every adjacent pair in the subsequence:

• If the two values are equal, it does not count against the limit.
• If the two values are different, it counts as one change.

The subsequence is valid if the total number of such changes is at most k.

For example, suppose the subsequence is:

[1, 1, 2, 2, 3]

The transitions are:

• 1 -> 1, same, no cost
• 1 -> 2, different, cost 1
• 2 -> 2, same, no cost
• 2 -> 3, different, cost 1

So this subsequence has exactly 2 changes.

The goal is to maximize the subsequence length while keeping the number of changes within the allowed limit.

The constraints are important:

• nums.length <= 500
• k <= 25

The array is relatively small, which strongly suggests that a dynamic programming solution is appropriate. An exponential brute-force search over all subsequences would be far too slow because there are 2^n possible subsequences.

Several edge cases are important:

• k = 0, meaning all adjacent elements in the subsequence must be equal
• Arrays where every value is distinct
• Arrays where all values are identical
• Small arrays of length 1
• Large k, where almost any subsequence becomes valid

The problem guarantees that k is non-negative and bounded by the array length, so we never need to handle invalid inputs.

Approaches

Brute Force

The brute-force solution is to generate every possible subsequence and check whether it is good.

For each subsequence:

1. Traverse the subsequence.
2. Count how many adjacent pairs differ.
3. If the count is at most k, update the maximum length.

This approach is correct because it explicitly checks every possible subsequence, so the optimal answer cannot be missed.

However, the time complexity is exponential. An array of length n has 2^n subsequences. With n = 500, this is completely infeasible.

Key Insight

The important observation is that the only information that matters when extending a subsequence is:

• The last value in the subsequence
• How many transitions have been used so far
• The current subsequence length

This naturally leads to dynamic programming.

Suppose we process the array from left to right. For every index i, we try to end a good subsequence at nums[i].

If we previously ended a subsequence at index j:

• If nums[j] == nums[i], extending the subsequence does not increase the transition count.
• Otherwise, extending it increases the transition count by 1.

So we can define a DP state that tracks:

dp[i][t]

Meaning:

The maximum length of a good subsequence ending at index i using exactly t transitions.

We then transition from all earlier positions j < i.

Because n <= 500 and k <= 25, an O(n^2 * k) solution is efficient enough.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generates every subsequence
Optimal Dynamic Programming	O(n^2 * k)	O(n * k)	Tracks best subsequences ending at each index

Algorithm Walkthrough

1. Create a 2D DP table dp.

Define:

dp[i][t]

as the maximum length of a good subsequence ending at index i with exactly t transitions. 2. Initialize every state to 1.

Every single element by itself forms a valid subsequence of length 1 with 0 transitions. 3. Process indices from left to right.

For every index i, examine all previous indices j < i. 4. Try extending subsequences ending at j.

For every possible transition count t:

• If nums[j] == nums[i], extending does not add a transition.
• Otherwise, extending adds one transition.

5. Update the DP state.

If the values are equal:

dp[i][t] = max(dp[i][t], dp[j][t] + 1)

If the values are different and t + 1 <= k:

dp[i][t + 1] = max(dp[i][t + 1], dp[j][t] + 1)

6. Track the global maximum.

After updating states, keep track of the best subsequence length seen so far. 7. Return the maximum answer.

Why it works

The DP invariant is:

dp[i][t] always stores the maximum length of a valid subsequence ending at index i using exactly t transitions.

Every valid subsequence ending at i must come from some earlier index j. The transition between nums[j] and nums[i] either preserves the transition count or increases it by one. Since the DP explores all such previous states, it considers every possible valid subsequence.

Therefore, the global maximum over all states is the optimal answer. Let's carefully build a complete technical solution guide for LeetCode 3176 following your exact formatting and requirements.

Problem Understanding

The problem asks us to find the maximum length of a subsequence of an array nums such that the subsequence is good. A subsequence is considered good if there are at most k positions where consecutive elements are different.

Restated, we are allowed to pick any subsequence of nums, but we can only tolerate up to k “changes” between consecutive numbers. The output is the length of the longest subsequence satisfying this property.

The input nums is an array of integers, potentially large (1 <= nums[i] <= 10^9), and k is a small non-negative integer (0 <= k <= min(nums.length, 25)). The constraints indicate that a dynamic programming solution is feasible because nums.length is moderate (<= 500) and k is very small.

Important edge cases include sequences where all elements are identical, where k = 0, or where k is large relative to the number of unique elements. Naive implementations that attempt to generate all subsequences would be too slow because the number of subsequences grows exponentially.

Approaches

Brute-Force Approach

A brute-force approach would attempt to generate all possible subsequences of nums, calculate the number of positions where consecutive elements differ, and keep track of the longest one that satisfies the k-difference rule. This approach is correct because it exhaustively checks every possible option.

However, the number of subsequences of an array of length n is 2^n. For n = 500, this is astronomically large, making brute-force infeasible.

Optimal Approach

The key insight is that the number of allowed “differences” k is small, so we can use dynamic programming to track subsequences efficiently. We can define a DP table dp[i][j] where i is the current index in nums and j is the number of differences used so far.

At each element, we can either include it or skip it. If we include it, we check whether it matches the last chosen number in the subsequence. If it matches, no extra difference is used; if it differs, we increment the difference counter. The optimal subsequence length is the maximum value in the DP table after processing all elements.

By using memoization, we avoid recalculating subproblems and reduce exponential complexity to polynomial time in n and k.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generate all subsequences, check differences
Optimal	O(n * k)	O(n * k)	DP approach using last element and used differences

Algorithm Walkthrough

1. Initialize a DP table dp where dp[i][j] represents the maximum length of a good subsequence ending at index i using j differences. Each entry starts with a default value of 1 for using just nums[i] alone.
2. Iterate over the array with index i from 0 to n - 1. For each i, iterate over all previous indices p < i.
3. For each pair (p, i), consider extending the subsequence ending at p by including nums[i].
4. If nums[i] == nums[p], including nums[i] does not consume a difference. Update dp[i][j] accordingly.
5. If nums[i] != nums[p], including nums[i] consumes one additional difference. Only update dp[i][j+1] if j+1 <= k.
6. After processing all indices, the answer is the maximum value in the DP table across all indices and all differences 0..k.

Why it works: The DP table maintains the invariant that dp[i][j] always stores the longest subsequence ending at i using exactly j differences. By considering each previous element and possible differences used, we ensure that no possible valid subsequence is missed, guaranteeing the optimal solution.

Python Solution

from typing import List

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)

        dp = [[1] * (k + 1) for _ in range(n)]

        answer = 1

        for i in range(n):
            for j in range(i):
                for transitions in range(k + 1):

                    if nums[i] == nums[j]:
                        dp[i][transitions] = max(
                            dp[i][transitions],
                            dp[j][transitions] + 1
                        )
                    else:
                        if transitions + 1 <= k:
                            dp[i][transitions + 1] = max(
                                dp[i][transitions + 1],
                                dp[j][transitions] + 1
                            )

            answer = max(answer, max(dp[i]))

        return answer

The implementation starts by creating a DP table of size n x (k + 1). Every entry is initialized to 1 because a single element always forms a valid subsequence.

The outer loop processes each index i. For every earlier index j, the algorithm attempts to extend subsequences ending at j.

The innermost loop iterates through all possible transition counts.

When nums[i] == nums[j], adding the current element does not introduce a new transition, so the same transition count is preserved.

When the values differ, one additional transition is consumed. The update only occurs if the new transition count remains within the allowed limit k.

The variable answer continuously tracks the maximum subsequence length found anywhere in the DP table. dp = [[0] * (k + 1) for _ in range(n)]

    for i in range(n):
        for j in range(k + 1):
            dp[i][j] = 1
    
    for i in range(n):
        for p in range(i):
            for j in range(k + 1):
                if nums[i] == nums[p]:
                    dp[i][j] = max(dp[i][j], dp[p][j] + 1)
                elif j > 0:
                    dp[i][j] = max(dp[i][j], dp[p][j - 1] + 1)
    
    return max(max(row) for row in dp)

The Python implementation initializes the DP table with length 1 subsequences for each element. It then iterates over all pairs of indices to compute whether adding the current element will extend a subsequence without exceeding the difference limit `k`. Finally, it finds the maximum value in the DP table, which corresponds to the longest good subsequence.

## Go Solution

```go
func maximumLength(nums []int, k int) int {
	n := len(nums)

	dp := make([][]int, n)

	for i := 0; i < n; i++ {
		dp[i] = make([]int, k+1)

		for t := 0; t <= k; t++ {
			dp[i][t] = 1
		}
	}

	answer := 1

	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			for transitions := 0; transitions <= k; transitions++ {

				if nums[i] == nums[j] {
					dp[i][transitions] = max(
						dp[i][transitions],
						dp[j][transitions]+1,
					)
				} else {
					if transitions+1 <= k {
						dp[i][transitions+1] = max(
							dp[i][transitions+1],
							dp[j][transitions]+1,
						)
					}
				}
			}
		}

		for t := 0; t <= k; t++ {
			answer = max(answer, dp[i][t])
		}
	}

	return answer
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the same DP logic as the Python version.

Since Go does not provide a built-in max function for integers, a helper function is defined.

The DP table is implemented using a slice of slices. Each state is initialized to 1 for the same reason as in Python, every element alone forms a valid subsequence.

No special handling for integer overflow is needed because the maximum subsequence length is at most 500.

Worked Examples

Example 1

nums = [1, 2, 1, 1, 3]
k = 2

We build the DP table progressively.

Initial state:

Index	Value	dp[i][0]	dp[i][1]	dp[i][2]
0	1	1	1	1

Processing index 1, value = 2

Compare with index 0:

• 1 != 2
• Transition count increases by 1

Update:

dp[1][1] = dp[0][0] + 1 = 2

State:

Index	Value	dp[i][0]	dp[i][1]	dp[i][2]
0	1	1	1	1
1	2	1	2	2

Processing index 2, value = 1

Compare with index 0:

• Same value
• No extra transition

dp[2][0] = 2

Compare with index 1:

• Different value
• Add one transition

dp[2][2] = dp[1][1] + 1 = 3

State:

Index	Value	dp[i][0]	dp[i][1]	dp[i][2]
2	1	2	2	3

Processing index 3, value = 1

Compare with previous 1s:

dp[3][0] = 3
dp[3][2] = 4

Now we have subsequence:

[1, 2, 1, 1]

Length 4 with 2 transitions.

Processing index 4, value = 3

Extending previous states gives maximum length 4.

Final answer:

4

Example 2

nums = [1, 2, 3, 4, 5, 1]
k = 0

Since k = 0, no adjacent unequal values are allowed.

Therefore, the subsequence must contain only repeated occurrences of the same value.

The best choice is:

[1, 1]

Length:

2

The DP only allows transitions where adjacent values are equal because adding a different value would require one transition, which exceeds k. n := len(nums) dp := make([][]int, n) for i := 0; i < n; i++ { dp[i] = make([]int, k+1) for j := 0; j <= k; j++ { dp[i][j] = 1 } }

for i := 0; i < n; i++ {
    for p := 0; p < i; p++ {
        for j := 0; j <= k; j++ {
            if nums[i] == nums[p] {
                if dp[p][j]+1 > dp[i][j] {
                    dp[i][j] = dp[p][j] + 1
                }
            } else if j > 0 {
                if dp[p][j-1]+1 > dp[i][j] {
                    dp[i][j] = dp[p][j-1] + 1
                }
            }
        }
    }
}

maxLen := 0
for i := 0; i < n; i++ {
    for j := 0; j <= k; j++ {
        if dp[i][j] > maxLen {
            maxLen = dp[i][j]
        }
    }
}
return maxLen

}

In Go, we pre-allocate the 2D slice `dp` and initialize each entry with 1. The main loop logic mirrors the Python approach, taking care to check for slice bounds and updating the maximum in-place.

## Worked Examples

### Example 1: nums = [1,2,1,1,3], k = 2

| i | nums[i] | dp[i][0] | dp[i][1] | dp[i][2] |
| --- | --- | --- | --- | --- |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 2 | 1 | 2 | 0 |
| 2 | 1 | 2 | 3 | 0 |
| 3 | 1 | 3 | 4 | 0 |
| 4 | 3 | 1 | 4 | 4 |

Maximum length is 4.

### Example 2: nums = [1,2,3,4,5,1], k = 0

| i | nums[i] | dp[i][0] |
| --- | --- | --- |
| 0 | 1 | 1 |
| 1 | 2 | 1 |
| 2 | 3 | 1 |
| 3 | 4 | 1 |
| 4 | 5 | 1 |
| 5 | 1 | 2 |

Maximum length is 2 (only identical consecutive elements can extend).

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n^2 * k) | For every pair `(i, j)`, all transition counts are processed |
| Space | O(n * k) | DP table stores states for every index and transition count |

The algorithm uses three nested loops:

- One over `i`
- One over `j`
- One over transition counts

Since `k <= 25`, the extra factor is small and efficient in practice.

The space usage comes entirely from the DP table.

## Test Cases

```python
from typing import List

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)

        dp = [[1] * (k + 1) for _ in range(n)]

        answer = 1

        for i in range(n):
            for j in range(i):
                for transitions in range(k + 1):

                    if nums[i] == nums[j]:
                        dp[i][transitions] = max(
                            dp[i][transitions],
                            dp[j][transitions] + 1
                        )
                    else:
                        if transitions + 1 <= k:
                            dp[i][transitions + 1] = max(
                                dp[i][transitions + 1],
                                dp[j][transitions] + 1
                            )

            answer = max(answer, max(dp[i]))

        return answer

sol = Solution()

assert sol.maximumLength([1, 2, 1, 1, 3], 2) == 4  # provided example
assert sol.maximumLength([1, 2, 3, 4, 5, 1], 0) == 2  # provided example
assert sol.maximumLength([1], 0) == 1  # single element
assert sol.maximumLength([5, 5, 5, 5], 0) == 4  # all equal
assert sol.maximumLength([1, 2, 3, 4], 3) == 4  # enough transitions for all
assert sol.maximumLength([1, 2, 1, 2, 1], 1) == 3  # only one change allowed
assert sol.maximumLength([1, 2, 2, 2, 3], 1) == 4  # one transition optimal
assert sol.maximumLength([1, 2, 3, 1, 2, 3], 2) == 4  # multiple transition paths
assert sol.maximumLength([7, 7, 7, 1, 1, 7], 1) == 5  # repeated groups
assert sol.maximumLength([1, 2, 3, 4, 5], 0) == 1  # all distinct with no transitions

Test	Why
[1,2,1,1,3], k=2	Validates the main example
[1,2,3,4,5,1], k=0	Ensures no transitions are allowed
[1], k=0	Smallest possible input
[5,5,5,5], k=0	All elements equal
[1,2,3,4], k=3	Entire array can be taken
[1,2,1,2,1], k=1	Transition limit blocks full array
[1,2,2,2,3], k=1	Long repeated segment
[1,2,3,1,2,3], k=2	Multiple competing subsequences
[7,7,7,1,1,7], k=1	Large equal blocks
[1,2,3,4,5], k=0	Distinct values with strict limit

Edge Cases

Case 1, k = 0

When no transitions are allowed, the subsequence must consist entirely of identical values. A buggy implementation might still allow transitions accidentally when extending states.

The DP handles this correctly because transitions to different values only occur when transitions + 1 <= k. When k = 0, such updates are never allowed.

Case 2, all values are distinct

Consider:

[1, 2, 3, 4]

If k = 0, the answer must be 1 because every adjacent pair differs.

If k = 3, the whole array becomes valid.

This case verifies that the algorithm properly tracks the number of transitions rather than simply counting elements.

Case 3, all values are equal

Consider:

[5, 5, 5, 5]

No transitions are ever used, regardless of subsequence length.

A flawed implementation might incorrectly increase the transition count when extending subsequences.

The DP explicitly checks equality before deciding whether to increase the transition count, so equal values preserve the same transition budget.

Case 4, repeated values separated by other numbers

Consider:

[1, 2, 1, 2, 1]

The optimal subsequence may skip elements strategically.

This validates that the solution truly computes subsequences rather than contiguous subarrays. Since the DP transitions consider all previous indices j < i, skipping elements naturally works correctly. | Time | O(n^2 * k) | Nested loops over pairs of indices and difference states | | Space | O(n * k) | DP table of size n by k+1 |

The time complexity arises because for each index i we consider all previous indices p and all difference counts j. Space complexity comes from storing the DP values.

Test Cases

# provided examples
assert Solution().maximumLength([1,2,1,1,3], 2) == 4  # max good subsequence
assert Solution().maximumLength([1,2,3,4,5,1], 0) == 2  # no differences allowed

# edge cases
assert Solution().maximumLength([1,1,1,1], 0) == 4  # all identical
assert Solution().maximumLength([1,2,3,4,5], 5) ==