# Find the Maximum Length of a Good Subsequence I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-length-of-a-good-subsequence-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-length-of-a-good-subsequence-i
**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 <= 500`
* `1 <= nums[i] <= 109`
* `0 <= k <= min(nums.length, 25)`

# Approaches
## 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 that ends with the element `nums[i]` and has exactly `j` mismatches. To compute `dp[i][j]`, we iterate through all previous elements `nums[p]` (where `p < i`) and consider extending the subsequences ending at `p`. This leads to a cubic time complexity relative to the input size and `k`.
**Time:** O(n^2 * k), where `n` is the number of elements in `nums`. We have 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), where `n` is the number of elements in `nums`. This is for the 2D `dp` array.
**Pros:** The logic is a direct translation of the problem's recursive structure, making it relatively easy to understand.; It correctly solves the problem and passes within the given constraints.
**Cons:** The time complexity of `O(n^2 * k)` can be slow if the constraints on `n` were larger.; It is less efficient than the optimized DP approach.
### Explanation
The core idea is to build up solutions for subsequences of increasing length. For each element `nums[i]`, we consider it as the potential end of a new, longer subsequence. We look back at all preceding elements `nums[p]` and see if we can append `nums[i]` to a subsequence ending at `nums[p]`. The number of mismatches `j` is a crucial part of our state, as it determines whether we can append `nums[i]` if it's different from `nums[p]`. By systematically building this `dp` table, we ensure that we have considered all possible valid subsequences.

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

        for (int i = 0; i < n; i++) {
            // Initialize dp table for index i. A single element has length 1 and 0 mismatches.
            for (int j = 0; j <= k; j++) {
                dp[i][j] = 1;
            }

            // Iterate through all previous elements to extend their subsequences.
            for (int p = 0; p < i; p++) {
                if (nums[i] == nums[p]) {
                    // No new mismatch.
                    for (int j = 0; j <= k; j++) {
                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j]);
                    }
                } else {
                    // New mismatch is created.
                    for (int j = 1; j <= k; j++) {
                        dp[i][j] = Math.max(dp[i][j], 1 + dp[p][j - 1]);
                    }
                }
            }
        }

        // The answer is the maximum value in the entire dp table.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
*   **State Definition:** Let `dp[i][j]` be the maximum length of a good subsequence that ends with the element `nums[i]` and has exactly `j` mismatches.
*   **Initialization:**
    *   Create a 2D array `dp` of size `n x (k+1)`, where `n` is the length of `nums`.
    *   Initialize all entries `dp[i][j]` to 1. This represents the base case where the subsequence consists of only the element `nums[i]`, which has a length of 1 and 0 mismatches.
*   **Transitions:**
    *   Iterate through the array `nums` with index `i` from `0` to `n-1`.
    *   For each `i`, iterate through all previous indices `p` from `0` to `i-1`.
    *   For each pair `(i, p)`, we consider extending the subsequences that ended at `p` with the element `nums[i]`.
        *   **Case 1: `nums[i] == nums[p]`**
            *   If the current element `nums[i]` is the same as the previous element `nums[p]`, no new mismatch is created.
            *   We can extend any subsequence ending at `p` with `j` mismatches. The new length will be `1 + dp[p][j]`.
            *   So, for each `j` from `0` to `k`, we update: `dp[i][j] = max(dp[i][j], 1 + dp[p][j])`.
        *   **Case 2: `nums[i] != nums[p]`**
            *   If `nums[i]` is different from `nums[p]`, a new mismatch is created.
            *   We can extend a subsequence ending at `p` that had `j-1` mismatches. This is only possible if `j > 0`.
            *   The new length will be `1 + dp[p][j-1]`.
            *   So, for each `j` from `1` to `k`, we update: `dp[i][j] = max(dp[i][j], 1 + dp[p][j-1])`.
*   **Final Answer:**
    *   The problem asks for the maximum length of a good subsequence with *at most* `k` mismatches. This means we need to find the maximum value in the entire `dp` table, as any entry `dp[i][j]` represents a valid good subsequence.
    *   The overall maximum length is the maximum value found in `dp` after all iterations.

## Optimized Dynamic Programming
This approach optimizes the previous DP solution by eliminating the `O(n)` inner loop. Instead of re-scanning all previous elements, we maintain the necessary information to make the transition in `O(1)` time. We keep track of two things: the maximum length of a subsequence ending with a specific value for a given number of mismatches, and the overall maximum length for a given number of mismatches.
**Time:** O(n * k), where `n` is the length of `nums`. We iterate through each of the `n` numbers, and for each, we perform `k+1` updates. Hash map operations take, on average, `O(1)` time. · **Space:** O(n * k) in the worst case. If all elements in `nums` are distinct, each of the `k+1` maps could store up to `n` entries. The `maxLen` array takes `O(k)` space.
**Pros:** Highly efficient with a time complexity of `O(n * k)`, which is optimal for the given constraints.; Effectively handles large value ranges for `nums[i]` by using hash maps.
**Cons:** The state management is more complex, involving hash maps and an auxiliary array.; The space complexity can be `O(n*k)` in the worst-case scenario where all numbers are distinct.
### Explanation
The key insight for optimization is that to calculate the new length for a subsequence ending in `num` with `j` mismatches, we only need two pieces of information from the state before processing `num`:
1.  The maximum length of a subsequence ending in `num` with `j` mismatches.
2.  The maximum length of *any* subsequence with `j-1` mismatches.

By storing these two types of information and updating them as we iterate through `nums`, we avoid the expensive `O(n)` scan for every element. We use an array of hash maps, `dp`, to store the first piece of information, and a simple array, `maxLen`, for the second. This reduces the time complexity from `O(n^2 * k)` to `O(n * k)`.

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

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

        // dp[j] is a map from value to max length of a subsequence ending with that value, using j mismatches.
        Map<Integer, Integer>[] dp = new HashMap[k + 1];
        for (int j = 0; j <= k; j++) {
            dp[j] = new HashMap<>();
        }

        // maxLen[j] stores the max length of any subsequence with j mismatches.
        int[] maxLen = new int[k + 1];
        int ans = 1;

        for (int num : nums) {
            // Iterate j from k down to 0 to use results from the previous element's iteration.
            for (int j = k; j >= 0; j--) {
                // Case 1: Extend a subsequence ending with the same value `num`.
                // No new mismatch is created.
                int lenSame = 1 + dp[j].getOrDefault(num, 0);

                // Case 2: Extend a subsequence ending with a different value.
                // A new mismatch is created. We need to have used j-1 mismatches before.
                int lenDiff = 0;
                if (j > 0) {
                    lenDiff = 1 + maxLen[j - 1];
                }

                // The new max length for a subsequence ending in `num` with `j` mismatches.
                int currentMax = Math.max(lenSame, lenDiff);
                
                // Update the DP state for the current number and mismatch count.
                dp[j].put(num, currentMax);
                
                // Update the overall max length for `j` mismatches.
                maxLen[j] = Math.max(maxLen[j], currentMax);
                
                // Update the global answer.
                ans = Math.max(ans, currentMax);
            }
        }
        return ans;
    }
}
```
### Algorithm
*   **State Definition:** We use two data structures to track the state:
    1.  `dp[j]`: A hash map for each mismatch count `j`. `dp[j][v]` stores the maximum length of a good subsequence with exactly `j` mismatches that ends with the value `v`.
    2.  `maxLen[j]`: An array where `maxLen[j]` stores the maximum length of *any* good subsequence with `j` mismatches found so far, irrespective of its ending value.
*   **Initialization:**
    *   Initialize `dp` as an array of `k+1` empty hash maps.
    *   Initialize `maxLen` as an array of size `k+1` with all zeros.
    *   Initialize `ans = 1` (assuming `n > 0`), as the minimum possible answer is 1.
*   **Transitions:**
    *   Iterate through each `num` in the input array `nums`.
    *   For each `num`, iterate through the number of mismatches `j` from `k` down to `0`. The downward iteration is crucial to prevent using information from the current `num`'s updates in the same pass.
    *   For each `j`, calculate the new maximum length for a subsequence ending in `num`:
        *   `len_same = 1 + dp[j].getOrDefault(num, 0)`: This is the length if we extend a previous subsequence that also ended in `num` (no new mismatch).
        *   `len_diff = 1 + maxLen[j-1]` (if `j > 0`): This is the length if we extend any subsequence with `j-1` mismatches (a new mismatch is formed).
    *   The new length for a subsequence ending in `num` with `j` mismatches is `currentMax = max(len_same, len_diff)`.
    *   Update the state: `dp[j].put(num, currentMax)` and `maxLen[j] = max(maxLen[j], currentMax)`.
*   **Final Answer:**
    *   The overall maximum length is tracked in a variable `ans`, which is updated in each step: `ans = max(ans, currentMax)`. After iterating through all numbers, `ans` holds 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];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int h = 0; h <= k; ++h) {
        for (int j = 0; j < i; ++j) {
          if (nums[i] == nums[j]) {
            f[i][h] = Math.max(f[i][h], f[j][h]);
          } else if (h > 0) {
            f[i][h] = Math.max(f[i][h], f[j][h - 1]);
          }
        }
        ++f[i][h];
      }
      ans = Math.max(ans, f[i][k]);
    }
    return ans;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) f = [[1] * (k + 1) for _ in range(n)] ans = 0 for i, x in enumerate(nums): for h in range(k + 1): for j, y in enumerate(nums[: i]): if x == y: f[i][h] = max(f[i][h], f[j][h] + 1) elif h: f[i][h] = max(f[i][h], f[j][h - 1] + 1) ans = max(ans, f[i][k]) return ans

```