# Find the Maximum Length of a Good Subsequence II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-maximum-length-of-a-good-subsequence-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-length-of-a-good-subsequence-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## 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`.

**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 <= 5 * 103`
* `1 <= nums[i] <= 109`
* `0 <= k <= min(50, nums.length)`

# Approaches
## Naive Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define a 2D DP table, `dp[i][j]`, to store the maximum length of a good subsequence ending at index `i` with exactly `j` "breaks" (where adjacent elements are different). To compute the value for `dp[i][j]`, we iterate through all previous elements `nums[p]` (where `p < i`) and consider extending the subsequences ending at `p`.
**Time:** O(N² * K), where N is the length of `nums`. There are three nested loops: iterating through `i` from `0` to `N-1`, `p` from `0` to `i-1`, and `j` from `0` to `K`. · **Space:** O(N * K), for the 2D DP table of size `n x (k+1)`.
**Pros:** The logic is a direct translation of the problem definition into a DP state, making it relatively easy to understand.
**Cons:** The time complexity of O(N² * K) is too high for the given constraints, leading to a Time Limit Exceeded (TLE) error.
### Explanation
In this method, we define `dp[i][j]` as the maximum length of a good subsequence of `nums[0...i]` that ends with `nums[i]` and has exactly `j` breaks. A break occurs when an element is different from the previous one in the subsequence.

To compute `dp[i][j]`, we look at all possible preceding elements `nums[p]` (where `p < i`) in the subsequence. Two cases arise:
1.  **`nums[p] == nums[i]`**: If we append `nums[i]` to a subsequence ending in `nums[p]`, the number of breaks does not change. Thus, we can extend any subsequence that ended at `p` with `j` breaks. The new length would be `dp[p][j] + 1`.
2.  **`nums[p] != nums[i]`**: If we append `nums[i]` to a subsequence ending in `nums[p]`, a new break is introduced. This means the subsequence ending at `p` must have had `j-1` breaks. The new length would be `dp[p][j-1] + 1`.

The base case is that any single element `nums[i]` forms a subsequence of length 1 with 0 breaks. The final answer is the maximum value across the entire `dp` table, since the optimal subsequence can end at any index `i` and use any number of breaks `j` from `0` to `k`.

```java
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return 0;
        
        // dp[i][j]: max length of a good subsequence ending at index i with j breaks.
        int[][] dp = new int[n][k + 1];
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            // A subsequence with only nums[i] has length 1 and 0 breaks.
            dp[i][0] = 1;
            
            for (int p = 0; p < i; p++) {
                if (nums[p] == nums[i]) {
                    // Same element, no new break.
                    for (int j = 0; j <= k; j++) {
                        if (dp[p][j] > 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[p][j] + 1);
                        }
                    }
                } else {
                    // Different element, one new break.
                    for (int j = 1; j <= k; j++) {
                        if (dp[p][j - 1] > 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[p][j - 1] + 1);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n][k+1]`, where `dp[i][j]` stores the maximum length of a good subsequence ending at index `i` with exactly `j` breaks.
- Initialize a variable `maxLength` to 1, as any single element is a valid subsequence of length 1.
- Iterate through each element `nums[i]` from `i = 0` to `n-1`.
- For each `nums[i]`, initialize `dp[i][0] = 1` (a subsequence with just `nums[i]` has length 1 and 0 breaks).
- Iterate through all previous elements `nums[p]` where `p < i`.
- If `nums[p] == nums[i]`, we can extend a subsequence ending at `p` without adding a break. For each `j` from `0` to `k`, update `dp[i][j] = max(dp[i][j], dp[p][j] + 1)`.
- If `nums[p] != nums[i]`, we introduce a new break. For each `j` from `1` to `k`, we can extend a subsequence that ended at `p` with `j-1` breaks. Update `dp[i][j] = max(dp[i][j], dp[p][j-1] + 1)`.
- After filling the `dp` table, the answer is the maximum value found in the entire `dp` table, as the subsequence can end at any index with any number of breaks up to `k`.

## Optimized Dynamic Programming
This approach significantly optimizes the naive DP solution by eliminating the innermost loop. Instead of re-scanning all previous elements for each state, we maintain auxiliary data structures that store the necessary maximum lengths. This allows us to compute the DP transitions in constant time (on average), reducing the overall time complexity.
**Time:** O(N * K), where N is the length of `nums`. We have a loop through `nums` (N iterations) and a nested loop for `k` (K iterations). The map operations inside take, on average, O(1) time. · **Space:** O(D * K), where D is the number of distinct elements in `nums`. In the worst case, D can be up to N, making the space complexity O(N * K).
**Pros:** Highly efficient with a time complexity of O(N * K), which passes the given constraints.; Effectively solves the problem by optimizing the DP state transitions.
**Cons:** The space complexity can be high, up to O(D * K) where D is the number of distinct elements, which can be O(N * K) in the worst case.; The logic is more complex than the naive DP approach, involving multiple data structures and a specific loop order.
### Explanation
The key observation for optimization is that to calculate the max length of a subsequence ending with `nums[i]` and `j` breaks, we only need two pieces of information from the state before processing `nums[i]`:
1. The max length of a subsequence ending with the same value `nums[i]` using `j` breaks.
2. The max length of *any* subsequence using `j-1` breaks (to which we can append `nums[i]` to create a new break).

We can maintain these values as we iterate through `nums`. We use an array of HashMaps, `maxLenForVal`, to track the first piece of information, and a simple array, `maxLenOverall`, for the second. For each element `num` in `nums`, we calculate the best possible lengths for subsequences ending with `num` for all possible break counts `j`. Then, we use these new lengths to update our two tracking structures.

By iterating `j` from `k` down to `0`, we cleverly use the `maxLenOverall` values from the state *before* processing the current `num`, avoiding the need for a temporary array to store intermediate results for the current element.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;

        // maxLenForVal[j] is a map from value -> maxLength for a subsequence with j breaks
        Map<Integer, Integer>[] maxLenForVal = new HashMap[k + 1];
        for (int i = 0; i <= k; i++) {
            maxLenForVal[i] = new HashMap<>();
        }

        // maxLenOverall[j] is the max length of any subsequence with j breaks
        int[] maxLenOverall = new int[k + 1];

        for (int num : nums) {
            for (int j = k; j >= 0; j--) {
                // Case 1: The previous element in the subsequence is the same as num.
                // The number of breaks remains j.
                int lenSame = 1 + maxLenForVal[j].getOrDefault(num, 0);

                // Case 2: The previous element is different from num.
                // This introduces a new break, so the previous subsequence had j-1 breaks.
                int lenDiff = 1;
                if (j > 0) {
                    lenDiff = 1 + maxLenOverall[j - 1];
                }

                // The max length for a subsequence ending with num and having j breaks
                int currentMaxLen = Math.max(lenSame, lenDiff);

                // Update the states for the next element
                maxLenForVal[j].put(num, currentMaxLen);
                maxLenOverall[j] = Math.max(maxLenOverall[j], currentMaxLen);
                
                ans = Math.max(ans, currentMaxLen);
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize two main data structures:
  - `maxLenForVal`: An array of `k+1` HashMaps. `maxLenForVal[j]` will map a number `v` to the maximum length of a subsequence ending with `v` using `j` breaks.
  - `maxLenOverall`: An array of size `k+1`. `maxLenOverall[j]` will store the overall maximum length of any subsequence with `j` breaks, irrespective of the ending value.
- Initialize `ans = 0`.
- Iterate through each `num` in the input array `nums`.
- For each `num`, iterate `j` from `k` down to `0`. This downward iteration is crucial to ensure we use the state from *before* processing the current `num`.
- Inside the loop, calculate the maximum length of a subsequence ending with `num` and `j` breaks. This is the maximum of two possibilities:
  1. Extending a subsequence ending with the same number `num`: `1 + maxLenForVal[j].getOrDefault(num, 0)`.
  2. Extending a subsequence ending with a different number (creating a break): `1 + maxLenOverall[j-1]` (only if `j > 0`).
- Let this new length be `currentMaxLen`.
- Update the state for subsequent elements: `maxLenForVal[j].put(num, currentMaxLen)` and `maxLenOverall[j] = max(maxLenOverall[j], currentMaxLen)`.
- Update the overall answer: `ans = max(ans, currentMaxLen)`.
- After iterating through all numbers, `ans` will hold the result.

# Solutions
### Java

```java
class Solution {
public
  int maximumLength(int[] nums, int k) {
    int n = nums.length;
    int[][] f = new int[n][k + 1];
    Map<Integer, Integer>[] mp = new HashMap[k + 1];
    Arrays.setAll(mp, i->new HashMap<>());
    int[][] g = new int[k + 1][3];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int h = 0; h <= k; ++h) {
        f[i][h] = mp[h].getOrDefault(nums[i], 0);
        if (h > 0) {
          if (g[h - 1][0] != nums[i]) {
            f[i][h] = Math.max(f[i][h], g[h - 1][1]);
          } else {
            f[i][h] = Math.max(f[i][h], g[h - 1][2]);
          }
        }
        ++f[i][h];
        mp[h].merge(nums[i], f[i][h], Integer : : max);
        if (g[h][0] != nums[i]) {
          if (f[i][h] >= g[h][1]) {
            g[h][2] = g[h][1];
            g[h][1] = f[i][h];
            g[h][0] = nums[i];
          } else {
            g[h][2] = Math.max(g[h][2], f[i][h]);
          }
        } else {
          g[h][1] = Math.max(g[h][1], f[i][h]);
        }
        ans = Math.max(ans, f[i][h]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumLength(vector<int> &nums, int k) {
    int n = nums.size();
    vector<vector<int>> f(n, vector<int>(k + 1));
    vector<unordered_map<int, int>> mp(k + 1);
    vector<vector<int>> g(k + 1, vector<int>(3));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int h = 0; h <= k; ++h) {
        f[i][h] = mp[h][nums[i]];
        if (h > 0) {
          if (g[h - 1][0] != nums[i]) {
            f[i][h] = max(f[i][h], g[h - 1][1]);
          } else {
            f[i][h] = max(f[i][h], g[h - 1][2]);
          }
        }
        ++f[i][h];
        mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]);
        if (g[h][0] != nums[i]) {
          if (f[i][h] >= g[h][1]) {
            g[h][2] = g[h][1];
            g[h][1] = f[i][h];
            g[h][0] = nums[i];
          } else {
            g[h][2] = max(g[h][2], f[i][h]);
          }
        } else {
          g[h][1] = max(g[h][1], f[i][h]);
        }
        ans = max(ans, f[i][h]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) f = [[0] * (k + 1) for _ in range(n)] mp = [defaultdict(int) for _ in range(k + 1)] g = [[0] * 3 for _ in range(k + 1)] ans = 0 for i, x in enumerate(nums): for h in range(k + 1): f[i][h] = mp[h][x] if h: if g[h - 1][0] != nums[i]: f[i][h] = max(f[i][h], g[h - 1][1]) else: f[i][h] = max(f[i][h], g[h - 1][2]) f[i][h] += 1 mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]) if g[h][0] != x: if f[i][h] >= g[h][1]: g[h][2] = g[h][1] g[h][1] = f[i][h] g[h][0] = x else: g[h][2] = max(g[h][2], f[i][h]) else: g[h][1] = max(g[h][1], f[i][h]) ans = max(ans, f[i][h]) return ans

```