Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming

Solution

LeetCode 3177 - Find the Maximum Length of a Good Subsequence II

Problem Understanding

We are given an integer array nums and a non-negative integer k. We must 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 without changing the relative order of the remaining elements. The subsequence does not need to be contiguous.

The important condition is about transitions between consecutive elements in the subsequence. Suppose the subsequence is:

[a1, a2, a3, ..., am]

We count how many positions satisfy:

ai != ai+1

That count must be at most k.

For example, if the subsequence is:

[1, 1, 2, 2, 2, 3]

the unequal adjacent pairs are:

1 -> 2
2 -> 3

So the number of changes is 2.

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

The constraints are important:

nums.length <= 5000
k <= 50

The array can be moderately large, but k is very small. This strongly suggests a dynamic programming solution where one dimension is based on k.

Several edge cases are important:

k = 0, meaning every adjacent pair in the subsequence must be equal. In this case, the answer becomes the maximum frequency of any number.
All numbers are distinct. Then every adjacent pair changes value.
All numbers are equal. Then we can always take the entire array regardless of k.
Large repeated groups mixed with isolated values.
Very small arrays such as length 1.

Approaches

Brute Force Approach

A brute force solution would generate every possible subsequence and check whether it is good.

For each subsequence:

Count the number of adjacent unequal pairs.
If that count is at most k, update the maximum length.

This is correct because it exhaustively checks all possibilities.

However, an array of length n has 2^n subsequences. With n = 5000, this is completely impossible.

Even a dynamic programming approach that compares every previous state naively can become too slow if not optimized carefully.

Key Insight

The important observation is that when extending a subsequence with a new number x, only two situations matter:

The previous subsequence already ended with x

Appending x does not increase the number of changes.

The previous subsequence ended with a different value

Appending x increases the number of changes by 1.

This suggests dynamic programming based on:

the ending value
the number of changes used

We define:

dp[c][x]

as the maximum length of a good subsequence:

ending with value x
using exactly c changes

To transition efficiently, we also maintain:

best[c]

which stores the best subsequence length using exactly c changes regardless of ending value.

This allows us to avoid scanning all previous values for every transition.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerates all subsequences
Optimal Dynamic Programming	O(n * k)	O(distinct_values * k)	Uses DP by ending value and transition count

Algorithm Walkthrough

Step 1: Define the DP State

We maintain:

dp[value][changes]

which represents the maximum subsequence length:

ending with value
using exactly changes unequal adjacent pairs

We also maintain:

best[changes]

which stores the global best subsequence length for that number of changes.

Step 2: Process Numbers One by One

We iterate through nums from left to right.

Suppose the current number is x.

We try to update all possible states ending with x.

Step 3: Extend Subsequences Without Adding a Change

If we already have a subsequence ending with x, we can append another x.

The number of changes stays the same.

So:

dp[x][c] + 1

is a valid transition.

Step 4: Extend Subsequences By Adding a Change

We may also append x to a subsequence ending with a different value.

If the previous subsequence used c - 1 changes, appending a different value creates one additional change.

The best such subsequence length is:

best[c - 1] + 1

Step 5: Update in Reverse Order

We process changes from k down to 0.

Reverse iteration prevents the current number from being reused multiple times within the same iteration.

Step 6: Update Global Best

After updating dp[x][c], we update:

best[c]

to keep track of the best subsequence length overall.

Why It Works

The DP invariant is:

dp[x][c]

always stores the maximum valid subsequence length ending with x using exactly c changes after processing the current prefix of the array.

Every valid subsequence extension falls into one of two categories:

appending the same value
appending a different value

The algorithm explicitly handles both cases, so every valid subsequence is considered. Since transitions always maximize lengths, the final answer is optimal.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = defaultdict(lambda: [0] * (k + 1))
        best = [0] * (k + 1)

        for num in nums:
            current = dp[num][:]

            for changes in range(k, -1, -1):
                current[changes] = max(current[changes], dp[num][changes] + 1)

                if changes > 0:
                    current[changes] = max(
                        current[changes],
                        best[changes - 1] + 1
                    )

                best[changes] = max(best[changes], current[changes])

            dp[num] = current

        return max(best)

The solution uses a hash map where each value maps to an array of DP states indexed by the number of changes used.

The dp[num][changes] state stores the best subsequence ending with num.

For each number:

We copy the current DP row because updates must not interfere with transitions in the same iteration.
We try extending subsequences ending with the same value.
We try extending the globally best subsequence with one additional change.
We update the global best values.

The reverse iteration over changes ensures correctness because each array element may only be used once.

Go Solution

package main

func maximumLength(nums []int, k int) int {
	dp := make(map[int][]int)
	best := make([]int, k+1)

	for _, num := range nums {
		if _, exists := dp[num]; !exists {
			dp[num] = make([]int, k+1)
		}

		current := make([]int, k+1)
		copy(current, dp[num])

		for changes := k; changes >= 0; changes-- {
			if dp[num][changes]+1 > current[changes] {
				current[changes] = dp[num][changes] + 1
			}

			if changes > 0 && best[changes-1]+1 > current[changes] {
				current[changes] = best[changes-1] + 1
			}

			if current[changes] > best[changes] {
				best[changes] = current[changes]
			}
		}

		dp[num] = current
	}

	answer := 0
	for _, value := range best {
		if value > answer {
			answer = value
		}
	}

	return answer
}

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

A map[int][]int is used instead of Python's defaultdict. Since Go maps return zero values automatically only for missing scalar types, we explicitly initialize slices for unseen numbers.

The copy() function is used to clone the DP state before modification.

Integer overflow is not a concern because the maximum subsequence length is at most 5000.

Worked Examples

Example 1

Input:

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

We maintain:

best[0], best[1], best[2]

Initial state:

Step	Number	best
Start	-	[0,0,0]

Processing 1:

changes	Transition	Result
0	start new subsequence	1

State:

best = [1,1,1]

Processing 2:

For changes = 1:

best[0] + 1 = 2

We can form:

[1,2]

State:

best = [1,2,2]

Processing second 1:

We can extend:

[1]

to:

[1,1]

or extend:

[1,2]

to:

[1,2,1]

State becomes:

best = [2,3,3]

Processing third 1:

We extend again:

[1,2,1]

to:

[1,2,1,1]

State:

best = [3,4,4]

Processing 3:

We append 3 to the best subsequence using one fewer change:

[1,2,1,1] + 3

This produces length 5 with 2 changes.

Final answer:

Example 2

Input:

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

Since k = 0, adjacent elements in the subsequence must all be equal.

The best strategy is to take repeated occurrences of the same number.

The value 1 appears twice.

So the answer is:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * k)	Each number processes all `k + 1` states
Space	O(distinct_values * k)	DP table for each distinct value

Since:

n <= 5000
k <= 50

the algorithm is efficient enough.

The number of DP transitions is at most:

5000 * 51 = 255000

which is very manageable.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = defaultdict(lambda: [0] * (k + 1))
        best = [0] * (k + 1)

        for num in nums:
            current = dp[num][:]

            for changes in range(k, -1, -1):
                current[changes] = max(current[changes], dp[num][changes] + 1)

                if changes > 0:
                    current[changes] = max(
                        current[changes],
                        best[changes - 1] + 1
                    )

                best[changes] = max(best[changes], current[changes])

            dp[num] = current

        return max(best)

sol = Solution()

assert sol.maximumLength([1,2,1,1,3], 2) == 5  # example with two changes
assert sol.maximumLength([1,2,3,4,5,1], 0) == 2  # no changes allowed
assert sol.maximumLength([1], 0) == 1  # single element
assert sol.maximumLength([7,7,7,7], 0) == 4  # all equal
assert sol.maximumLength([1,2,3,4], 3) == 4  # all changes allowed
assert sol.maximumLength([1,2,1,2,1,2], 1) == 4  # limited transitions
assert sol.maximumLength([1,1,2,2,3,3], 2) == 6  # grouped values
assert sol.maximumLength([1,2,3,1,2,3], 0) == 2  # best repeated value
assert sol.maximumLength([5,5,5,1,1,1,5], 1) == 7  # one transition
assert sol.maximumLength([1,2,1,2,1,2,1], 2) == 5  # alternating values

Test	Why
`[1,2,1,1,3], k=2`	Verifies general mixed transitions
`[1,2,3,4,5,1], k=0`	Ensures only equal-value subsequences are allowed
`[1], k=0`	Smallest possible input
`[7,7,7,7], k=0`	All elements identical
`[1,2,3,4], k=3`	Every transition allowed
`[1,2,1,2,1,2], k=1`	Alternating pattern with restricted changes
`[1,1,2,2,3,3], k=2`	Multiple grouped transitions
`[1,2,3,1,2,3], k=0`	Requires selecting repeated values only
`[5,5,5,1,1,1,5], k=1`	Long subsequence with one value switch
`[1,2,1,2,1,2,1], k=2`	Stress case with many alternating transitions

Edge Cases

Edge Case 1: `k = 0`

When no unequal adjacent pairs are allowed, every valid subsequence must contain only one distinct value.

A common bug is accidentally allowing transitions between different values even when k = 0.

The implementation handles this correctly because transitions from best[changes - 1] only occur when changes > 0.

Edge Case 2: All Values Are Distinct

Consider:

[1,2,3,4,5]

Every adjacent pair changes value.

If k is small, only short subsequences are valid.

The DP correctly limits transitions because each different appended value consumes one change.

Edge Case 3: All Values Are Equal

Consider:

[7,7,7,7,7]

No transitions are ever created.

The algorithm repeatedly extends the same-value state:

dp[7][0]

so the answer becomes the full array length.

Edge Case 4: Reusing Updated States Incorrectly

A subtle implementation bug occurs if updates are done in forward order.

That can accidentally allow the current element to be reused multiple times during one iteration.

The reverse iteration over changes and copying the current DP row prevent this issue completely.

LeetCode 3177 - Find the Maximum Length of a Good Subsequence II

Solution

LeetCode 3177 - Find the Maximum Length of a Good Subsequence II

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Step 1: Define the DP State

Step 2: Process Numbers One by One

Step 3: Extend Subsequences Without Adding a Change

Step 4: Extend Subsequences By Adding a Change

Step 5: Update in Reverse Order

Step 6: Update Global Best

Why It Works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Complexity Analysis

Test Cases

Edge Cases

Edge Case 1: k = 0

Edge Case 2: All Values Are Distinct

Edge Case 3: All Values Are Equal

Edge Case 4: Reusing Updated States Incorrectly

Edge Case 1: `k = 0`