Problem Statement

• 3202. Find the Maximum Length of Valid Subsequence II

Given an integer array nums and a positive integer k, find the maximum length of a valid subsequence. A subsequence is valid if all consecutive pairs in the subsequence have the same sum modulo k. Formally, for a subsequence sub of length x: (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x-2] + sub[x-1]) % k

Example 1:

• Input: nums = [1,2,3,4,5], k = 2
• Output: 5
• Explanation: The subsequence [1,2,3,4,5] is valid because (1+2)%2 = (2+3)%2 = (3+4)%2 = (4+5)%2 = 1

Example 2:

• Input: nums = [1,4,2,3,1,4], k = 3
• Output: 4
• Explanation: The subsequence [1,4,1,4] is valid because (1+4)%3 = (4+1)%3 = (1+4)%3 = 2

Algorithm Walkthrough

Key Insight

For a valid subsequence where all consecutive pairs sum to the same value target modulo k, the remainders must follow an alternating pattern. If we have r1 + r2 ≡ target (mod k), then the subsequence alternates between remainders r1 and r2.

Algorithm Steps

1. Handle Special Case: If k = 1, all numbers have remainder 0, so any subsequence is valid. Return the entire array length.

2. Preprocess Remainders: Convert all numbers to their remainders modulo k for easier processing.

3. Try All Target Sums: For each possible target sum i from 0 to k-1:

   • Use dynamic programming where dp[r] represents the maximum length of subsequence ending with remainder r and having target sum i

4. DP Transition: For each element with remainder arr[j]:

   • To achieve target sum i, the previous remainder must be (i - arr[j] + k) % k
   • Update: dp[arr[j]] = dp[(i - arr[j] + k) % k] + 1

5. Track Maximum: Keep track of the maximum length found across all target sums.

Detailed Example

For nums = [1,2,3,4,5], k = 2:

• Remainders: [1,0,1,0,1]
• When target sum i = 1:
  • Process 1 (remainder 1): previous should be (1-1+2)%2 = 0, dp[1] = dp[0] + 1 = 1
  • Process 2 (remainder 0): previous should be (1-0+2)%2 = 1, dp[0] = dp[1] + 1 = 2
  • Process 3 (remainder 1): previous should be (1-1+2)%2 = 0, dp[1] = dp[0] + 1 = 3
  • Process 4 (remainder 0): previous should be (1-0+2)%2 = 1, dp[0] = dp[1] + 1 = 4
  • Process 5 (remainder 1): previous should be (1-1+2)%2 = 0, dp[1] = dp[0] + 1 = 5

Complexity Analysis

• Time Complexity: O(k × n) where n is the length of the array. We iterate through all k possible target sums, and for each target sum, we process all n elements once.

• Space Complexity: O(k) for the DP array that stores the maximum length ending with each remainder, plus O(n) for the preprocessed remainder array, giving us O(n + k) total space.

Full Solution (Java)

The key insight of this solution is recognizing that valid subsequences follow alternating remainder patterns. By trying all possible target sums and using dynamic programming to track the maximum length ending with each remainder, we efficiently find the optimal subsequence without having to explicitly construct it.

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

        // Special case: if k = 1, all numbers have remainder 0
        // Any subsequence is valid since (0 + 0) % 1 = 0
        if (k == 1) {
            return length;
        }

        // Initialize result with minimum possible length (2 elements)
        int res = 2;

        // Preprocess: convert all numbers to their remainders mod k
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = nums[i] % k;
        }

        // Try all possible target sums from 0 to k-1
        for (int targetSum = 0; targetSum < k; targetSum++) {
            // dp[r] = maximum length of valid subsequence ending with remainder r
            // and having consecutive pairs that sum to targetSum mod k
            int[] dp = new int[k];

            // Process each element in the array
            for (int j = 0; j < length; j++) {
                int currentRemainder = arr[j];

                // To achieve targetSum, what should the previous remainder be?
                // If prev + current ≡ targetSum (mod k)
                // Then prev ≡ targetSum - current (mod k)
                int requiredPrevRemainder = (targetSum - currentRemainder + k) % k;

                // Extend the subsequence ending with requiredPrevRemainder
                dp[currentRemainder] = dp[requiredPrevRemainder] + 1;

                // Update global maximum
                res = Math.max(res, dp[currentRemainder]);
            }
        }

        return res;
    }
}

// Example trace for nums = [1,2,3,4,5], k = 2
/*
Remainders: [1,0,1,0,1]

Target sum = 0:
- Process 1 (rem=1): prev should be (0-1+2)%2=1, dp[1] = dp[1] + 1 = 1
- Process 2 (rem=0): prev should be (0-0+2)%2=0, dp[0] = dp[0] + 1 = 1  
- Process 3 (rem=1): prev should be (0-1+2)%2=1, dp[1] = dp[1] + 1 = 2
- Process 4 (rem=0): prev should be (0-0+2)%2=0, dp[0] = dp[0] + 1 = 2
- Process 5 (rem=1): prev should be (0-1+2)%2=1, dp[1] = dp[1] + 1 = 3
Max so far: 3

Target sum = 1:
- Process 1 (rem=1): prev should be (1-1+2)%2=0, dp[1] = dp[0] + 1 = 1
- Process 2 (rem=0): prev should be (1-0+2)%2=1, dp[0] = dp[1] + 1 = 2
- Process 3 (rem=1): prev should be (1-1+2)%2=0, dp[1] = dp[0] + 1 = 3  
- Process 4 (rem=0): prev should be (1-0+2)%2=1, dp[0] = dp[1] + 1 = 4
- Process 5 (rem=1): prev should be (1-1+2)%2=0, dp[1] = dp[0] + 1 = 5
Final result: 5
*/

The elegance of this approach lies in the mathematical relationship: if we want consecutive elements to sum to a target value modulo k, we can work backwards from the current element to determine what the previous element's remainder should be, enabling us to extend existing subsequences optimally.