3201. Find the Maximum Length of Valid Subsequence I

Time: O(n)

Space: O(1)

Problem Overview

Find the longest subsequence (not necessarily contiguous) where the sum of every adjacent pair is divisible by k (k = 2 in constraints).

Intuition

Find the longest subsequence (not necessarily contiguous) where the sum of every adjacent pair is divisible by k (k = 2 in constraints). Track DP by residues mod k: when adding nums[i], extend chains whose previous residue pairs to sum 0 mod k.

Algorithm

1Let freq[r1,r2] = longest valid subsequence length ending with residues r1 then r2.
2For each num in nums: r = num % k.
3For each prior residue j: y = (j - r + k) % k; update freq[r,y] = freq[y,r] + 1.
4Track global maximum length across all states.
5Return max length found.

Example Walkthrough

Input: nums with k=2 (parity)

1.Valid pairs must sum to even — chain even-even or odd-odd extensions.

Output: maximum valid subsequence length

Common Pitfalls

•Subsequence — elements need not be adjacent in the array.
•Modular arithmetic: use (j - r + k) % k for complement residue.
•Single-element subsequence length is 1 baseline.

3201.cs

// Approach: Greedily alternate parities; max of all-even, all-odd, alternating-even-start, alternating-odd-start.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaximumLength(int[] nums)
    {
        int k = 2; // Define the modulus value
        int[,] frequency = new int[k, k]; // Initialize a 2D array to hold frequency counts
        int maxLength = 0; // Variable to store the maximum length found

        for (int i = 0; i < nums.Length; i++) // Iterate over the elements in nums array
        {
            int num = nums[i];
            num %= k; // Calculate modulo of num with k
            for (int j = 0; j < k; ++j)
            { // Iterate over each possible value modulo k
                int y = (j - num + k) % k; // Calculate the required complement to make a sum divisible by k
                frequency[num, y] = frequency[y, num] + 1; // Update the frequency table with current element
                maxLength = Math.Max(maxLength, frequency[num, y]); // Update the maximum length found
            }
        }

        return maxLength; // Return the maximum length of subarray found
    }
}

Was this solution helpful?