3202. Find the Maximum Length of Valid Subsequence II

Time: O(n * k)

Space: O(k²)

Approach

DP dp[rem][last] = longest subsequence ending with value whose (prev+last)%k = rem.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.

3202.cs

// Approach: DP dp[rem][last] = longest subsequence ending with value whose (prev+last)%k = rem.
// Time: O(n * k) Space: O(k²)

public class Solution
{
    public int MaximumLength(int[] nums, int k)
    {
        // Initialize a 2D array to keep track of subarray lengths with modulo value
        int[,] subarrayLengths = new int[k, k];
        int maxLength = 0;  // Variable to store the maximum length found

        // Iterate over each element in nums
        foreach (int num in nums)
        {
            int modValue = num % k;  // Compute the current number's modulo with k

            // Iterate over all possible modulo values from 0 to k-1
            for (int j = 0; j < k; ++j)
            {
                int requiredMod = (j - modValue + k) % k;  // Compute the required complement modulo

                // Update the subarray length by 1 for the current modulo configuration
                subarrayLengths[modValue, requiredMod] = subarrayLengths[requiredMod, modValue] + 1;

                // Update the maximum length found so far
                maxLength = Math.Max(maxLength, subarrayLengths[modValue, requiredMod]);
            }
        }
        return maxLength;  // Return the maximum subarray length satisfying the condition
    }
}

Was this solution helpful?