# Find the Maximum Length of Valid Subsequence II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-length-of-valid-subsequence-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and a **positive** integer `k`. 

A subsequence `sub` of `nums` with length `x` is called **valid** if it satisfies:

* `(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.`
Return the length of the **longest** **valid** subsequence of `nums`. 

**Example 1:**

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

**Output:** 5

**Explanation:**

The longest valid subsequence is `[1, 2, 3, 4, 5]`.

**Example 2:**

**Input:** nums = \[1,4,2,3,1,4\], k = 3

**Output:** 4

**Explanation:**

The longest valid subsequence is `[1, 4, 1, 4]`.

**Constraints:**

* `2 <= nums.length <= 103`
* `1 <= nums[i] <= 107`
* `1 <= k <= 103`

# Approaches
## Brute-Force Check for All Remainder Pairs
This brute-force approach is based on a key observation about the structure of a valid subsequence. If a subsequence `sub` is valid, then `(sub[i-1] + sub[i]) % k` must be constant for all `i`. This implies that the sequence of remainders modulo `k` of the elements in `sub` must be alternating. For example, the remainders must follow a pattern like `r1, r2, r1, r2, ...`.

The algorithm leverages this by trying every possible pair of remainders `(r1, r2)`. For each of the `k*k` pairs, it iterates through the input array `nums` to find the longest subsequence that fits the alternating pattern. While simple to conceptualize, this method is computationally expensive due to its three nested loops.
**Time:** O(k^2 * N), where N is the number of elements in `nums` and k is the given integer. There are two nested loops for the remainder pairs (`k*k` iterations) and an inner loop that scans the entire `nums` array (N iterations). · **Space:** O(1), as it only uses a few variables to track the lengths and remainders.
**Pros:** The logic is straightforward once the alternating remainder property is understood.; It has a very low space complexity, `O(1)`.
**Cons:** The time complexity of `O(k^2 * N)` is too high for the given constraints (`N, k <= 1000`), which will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The algorithm works by exhaustively checking all possibilities for the two alternating remainders.

- First, we establish that any valid subsequence must have elements whose remainders modulo `k` alternate between two values, say `rem1` and `rem2`. This includes the case where `rem1 == rem2`, which corresponds to a subsequence where all elements have the same remainder.
- We initialize a variable `maxLength` to 1, as any single element is a valid subsequence.
- We then set up two nested loops, one for `rem1` from `0` to `k-1` and another for `rem2` from `0` to `k-1`.
- Inside these loops, for each pair `(rem1, rem2)`, we find the length of the longest valid subsequence with this specific alternating remainder pattern. We do this by iterating through `nums`, keeping track of the `neededRem` (which starts as `rem1` and flips to `rem2` and back) and a `currentLength`.
- If an element `nums[i]` has the `neededRem`, we increment `currentLength` and update `neededRem` to the other remainder in the pair.
- After checking all numbers for a given `(rem1, rem2)` pair, we update `maxLength = max(maxLength, currentLength)`.
- Finally, after checking all `k*k` pairs, `maxLength` will hold the answer.

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

        // Case where all elements have the same remainder
        for (int rem = 0; rem < k; rem++) {
            int count = 0;
            for (int num : nums) {
                if (num % k == rem) {
                    count++;
                }
            }
            maxLength = Math.max(maxLength, count);
        }

        // Case where remainders alternate between rem1 and rem2
        for (int rem1 = 0; rem1 < k; rem1++) {
            for (int rem2 = 0; rem2 < k; rem2++) {
                if (rem1 == rem2) continue;
                
                int currentLength = 0;
                int neededRem = rem1;
                for (int num : nums) {
                    if (num % k == neededRem) {
                        currentLength++;
                        // Flip the needed remainder
                        neededRem = (neededRem == rem1) ? rem2 : rem1;
                    }
                }
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. The fundamental insight is that for a subsequence to be valid, the remainders of its elements modulo `k` must form an alternating sequence, such as `r1, r2, r1, r2, ...`.
2. This approach iterates through every possible pair of starting remainders, `(rem1, rem2)`, where `0 <= rem1, rem2 < k`.
3. For each pair, it performs a linear scan through the `nums` array.
4. During the scan, it greedily builds the longest possible subsequence that adheres to the alternating `rem1, rem2` pattern.
5. It keeps a counter for the current subsequence length and tracks which remainder is needed next.
6. The global maximum length found across all `k*k` pairs is the result.

## Dynamic Programming
This approach uses dynamic programming to build the solution efficiently. It avoids the redundant computations of the brute-force method by storing intermediate results. The state of our DP is defined by the index of the last element in the subsequence and the remainder of the second-to-last element.

Let `dp[i][prev_rem]` be the length of the longest valid subsequence that ends with `nums[i]`, and whose previous element had a remainder of `prev_rem` when divided by `k`. By iterating through all possible previous elements `nums[j]` (where `j < i`), we can compute the value of `dp[i][nums[j] % k]` by extending a previously computed valid subsequence.
**Time:** O(N^2), due to the two nested loops iterating up to `N`. · **Space:** O(N * k) for the 2D DP table.
**Pros:** It is efficient enough to pass within the typical time limits for the given constraints.; The logic is a standard application of dynamic programming on subsequences.
**Cons:** The space complexity of `O(N*k)` can be large, potentially up to `1000*1000 = 10^6` elements, which might be a concern in memory-constrained environments.
### Explanation
The core of this DP approach is the recurrence relation that connects subsequences.

- We define `dp[i][rem]` as the length of the longest valid subsequence ending with `nums[i]`, where the element just before `nums[i]` in the subsequence has a remainder of `rem` modulo `k`.
- The DP table `dp` will have dimensions `N x k`.
- We iterate through each element `nums[i]` from `i = 0` to `N-1`.
- For each `nums[i]`, we consider it as the potential end of a valid subsequence. We then iterate through all preceding elements `nums[j]` (where `j < i`) as the potential second-to-last element.
- Let `rem_i = nums[i] % k` and `rem_j = nums[j] % k`.
- To extend a subsequence ending at `nums[j]` with `nums[i]`, the element before `nums[j]` must have had a remainder of `rem_i`. The length of such a subsequence is stored in `dp[j][rem_i]`. 
- If we find such a subsequence, its length is `dp[j][rem_i]`. By appending `nums[i]`, the new length becomes `dp[j][rem_i] + 1`. If no such subsequence exists (`dp[j][rem_i]` is 0), `nums[j]` and `nums[i]` form a new valid subsequence of length 2.
- The DP transition is: `dp[i][rem_j] = 1 + dp[j][rem_i]`. We initialize the `dp` table with 1s, representing single-element subsequences.
- We keep track of the maximum length found in the `dp` table.

```java
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int maxLength = 0;
        // dp[i][rem] = length of valid subsequence ending at index i,
        // with the previous element having a remainder of rem.
        int[][] dp = new int[n][k];

        for (int i = 0; i < n; i++) {
            // A single element is a subsequence of length 1.
            maxLength = Math.max(maxLength, 1);
            for (int j = 0; j < i; j++) {
                int rem_i = nums[i] % k;
                int rem_j = nums[j] % k;
                
                // The new subsequence is formed by extending a subsequence ending at j
                // where the element before j had a remainder of rem_i.
                // The length of that subsequence is dp[j][rem_i].
                // If dp[j][rem_i] is 0, it means we are starting a new sequence
                // with (nums[j], nums[i]), which has length 2.
                if (dp[j][rem_i] == 0) {
                    dp[i][rem_j] = 2;
                } else {
                    dp[i][rem_j] = dp[j][rem_i] + 1;
                }
                maxLength = Math.max(maxLength, dp[i][rem_j]);
            }
        }
        return maxLength == 0 ? (n > 0 ? 1 : 0) : maxLength;
    }
}
```
### Algorithm
1. Define a 2D DP table, `dp[i][rem]`, to store the length of the longest valid subsequence ending with the element `nums[i]`, where the second-to-last element in the subsequence has a remainder of `rem` modulo `k`.
2. Initialize the `dp` table of size `N x k` with zeros. Initialize `maxLength` to 1.
3. Iterate with `i` from `0` to `N-1` (for the last element of a potential subsequence).
4. Inside this loop, iterate with `j` from `0` to `i-1` (for the second-to-last element).
5. Let `rem_i = nums[i] % k` and `rem_j = nums[j] % k`.
6. A subsequence ending with `(...nums[p], nums[j])` can be extended by `nums[i]` if `(nums[p] + nums[j]) % k == (nums[j] + nums[i]) % k`. This simplifies to `nums[p] % k == nums[i] % k`.
7. The length of the subsequence ending at `j` with a preceding element of remainder `rem_i` is given by `dp[j][rem_i]`. 
8. The new length is `1 + dp[j][rem_i]`. Since any pair `(nums[j], nums[i])` forms a valid subsequence of length 2, the base length is 2.
9. The transition is: `dp[i][rem_j] = 1 + dp[j][rem_i]`. We initialize any new sequence with length 2, so we can consider `dp[j][rem_i]` to be 1 if it was 0.
10. A simpler transition is `dp[i][rem_j] = Math.max(dp[i][rem_j], 1 + (dp[j][rem_i] > 0 ? dp[j][rem_i] : 1))`. A more direct update is `dp[i][rem_j] = dp[j][rem_i] + 1`, assuming `dp` values are lengths and a length of 1 is the base for a single element.
11. Update `maxLength` with `dp[i][rem_j]` in each step.

## Optimized Dynamic Programming
This is the most efficient approach, further optimizing the dynamic programming solution. Instead of tracking the index of the last element, we only need to keep track of the remainders of the last two elements of a valid subsequence. This significantly reduces the state space of our DP table.

Let `dp[last_rem][prev_rem]` be the length of the longest valid subsequence whose last element has remainder `last_rem` and second-to-last element has remainder `prev_rem`. We process the `nums` array element by element. For each new number with remainder `c`, we can extend any existing valid subsequence that was 'waiting' for a `c`. A sequence ending in `...p, q` is waiting for a number with remainder `p`. So, when we see `c`, we look for sequences that ended in `...c, p` (for any `p`) and extend them.
**Time:** O(N * k), as we iterate through each of the `N` numbers and for each, we perform `k` updates. · **Space:** O(k^2) for the 2D DP table.
**Pros:** This is the most time-efficient solution for the given constraints.; The space complexity is independent of the input array size `N`, which is advantageous for very large arrays.
**Cons:** The space complexity of `O(k^2)` can be large if `k` is large, though it's independent of `N`.
### Explanation
This optimized DP approach focuses only on the necessary state information: the remainders.

- We define `dp[r1][r2]` as the length of the longest valid subsequence found so far whose elements' remainders alternate between `r1` and `r2`, and where the last element added had remainder `r1`.
- We initialize a `dp` table of size `k x k` with all zeros.
- We also initialize `maxLength = 1` to handle the case of single-element subsequences.
- We iterate through each `num` in the `nums` array.
- For each `num`, we get its remainder `c = num % k`.
- Then, we iterate through all possible preceding remainders `p` from `0` to `k-1`.
- A number with remainder `c` can extend an alternating sequence of `(c, p)` that previously ended with a `p`. The length of such a sequence is stored in `dp[p][c]`. 
- By adding the current number, we now have an alternating sequence of `(p, c)` ending with `c`, and its length becomes `dp[p][c] + 1`.
- So, the DP transition is `dp[c][p] = dp[p][c] + 1`.
- This single transition elegantly handles both extending a sequence and starting a new one (if `dp[p][c]` was 0, the new length becomes 1, which correctly represents the first element of that type being found). The total length is what we store.
- We update our global `maxLength` after each calculation.

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

        // dp[last_rem][prev_rem] stores the length of the LVS
        // ending with ... (prev_rem), (last_rem)
        int[][] dp = new int[k][k];

        for (int num : nums) {
            int current_rem = num % k;
            for (int prev_rem = 0; prev_rem < k; prev_rem++) {
                // A sequence ending in ... (current_rem), (prev_rem) is extended by num.
                // The new sequence ends in ... (prev_rem), (current_rem).
                // The new length is 1 + length of the old sequence.
                dp[current_rem][prev_rem] = dp[prev_rem][current_rem] + 1;
                maxLength = Math.max(maxLength, dp[current_rem][prev_rem]);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. The state of the DP can be optimized by removing the dependency on the index `i`.
2. Let `dp[last_rem][prev_rem]` be the length of the longest valid subsequence ending with an element of remainder `last_rem`, which was preceded by an element with remainder `prev_rem`.
3. Initialize a `dp` table of size `k x k` with zeros. Initialize `maxLength = 1`.
4. Iterate through each number `num` in the input array `nums`.
5. Let `c = num % k` be the remainder of the current number.
6. For each possible previous remainder `p` from `0` to `k-1`:
7. The current number `num` (with remainder `c`) can extend a subsequence that ended with `... (element with rem c), (element with rem p)`.
8. The length of such a subsequence is `dp[p][c]`. By appending `num`, the new subsequence ends with `... (element with rem p), (element with rem c)`.
9. The new length is `1 + dp[p][c]`. We update the state for this new ending pair: `dp[c][p] = 1 + dp[p][c]`.
10. The base case of a 2-element sequence is handled naturally. If `dp[p][c]` is 0, `dp[c][p]` becomes 1. This is incorrect for length. A better update is `dp[c][p] = dp[p][c] + 1`. This correctly counts the number of elements in the alternating sequence. For example, for a sequence of `p,c,p,c`, the lengths will be `dp[c][p]=1`, `dp[p][c]=2`, `dp[c][p]=3`.
11. Update `maxLength` with the new `dp[c][p]` value in every step.

# Solutions
### Java

```java
class Solution {
public
  int maximumLength(int[] nums, int k) {
    int[][] f = new int[k][k];
    int ans = 0;
    for (int x : nums) {
      x %= k;
      for (int j = 0; j < k; ++j) {
        int y = (j - x + k) % k;
        f[x][y] = f[y][x] + 1;
        ans = Math.max(ans, f[x][y]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumLength(vector<int> &nums, int k) {
    int f[k][k];
    memset(f, 0, sizeof(f));
    int ans = 0;
    for (int x : nums) {
      x %= k;
      for (int j = 0; j < k; ++j) {
        int y = (j - x + k) % k;
        f[x][y] = f[y][x] + 1;
        ans = max(ans, f[x][y]);
      }
    }
    return ans;
  }
};

```

### Python

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

```