3202. Find the Maximum Length of Valid Subsequence II

[mah-shamim]

Topics: Array, Dynamic Programming

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

Hint:

1. Fix the value of (subs[0] + subs[1]) % k from the k possible values. Let it be val.
2. Let dp[i] store the maximum length of a subsequence with its last element x such that x % k == i.
3. Answer for a subsequence ending at index y is dp[(k + val - (y % k)) % k] + 1.

Footnotes

1. Subsequence: A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. ↩

[mah-shamim]

We need to find the maximum length of a valid subsequence in an array where every consecutive pair of elements in the subsequence has the same modulo value when their sum is divided by a given integer k.

Approach

1. Problem Analysis: The key observation is that for any valid subsequence, all consecutive pairs of elements must satisfy (a + b) % k = val for some fixed value val. This condition implies that the residues of the elements in the subsequence must alternate between two residues r₀ and r₁ such that (r₀ + r₁) % k = val. Additionally, the subsequence can consist of elements with a single residue r₀ where (2 x r₀) % k = val.

2. Dynamic Programming Setup: For each possible value val (from 0 to k-1), we use a dynamic programming array dp where dp[r] stores the maximum length of a valid subsequence ending with an element whose residue is r under the current val.

3. Processing Elements: For each element in the array, compute its residue r = num % k. The required residue s for the previous element in the subsequence is given by s = (k + val - r) % k. The candidate length for the current element is either 1 (starting a new subsequence) or dp[s] + 1 (extending an existing subsequence ending with residue s).

4. Update DP State: Update dp[r] to the maximum of its current value and the candidate length. Track the maximum subsequence length encountered across all residues and all values of val.

5. Result Extraction: After processing all elements for all possible values of val, the maximum length found is the solution.

Let's implement this solution in PHP: 3202. Find the Maximum Length of Valid Subsequence II

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maximumLength($nums, $k) {
    $n = count($nums);
    $ans = 0;
    for ($val = 0; $val < $k; $val++) {
        $dp = array_fill(0, $k, 0);
        for ($i = 0; $i < $n; $i++) {
            $r = $nums[$i] % $k;
            $s = ($k + $val - $r) % $k;
            $candidate = 1;
            if ($dp[$s] > 0) {
                $candidate = $dp[$s] + 1;
            }
            if ($candidate > $dp[$r]) {
                $dp[$r] = $candidate;
            }
            if ($dp[$r] > $ans) {
                $ans = $dp[$r];
            }
        }
    }
    return $ans;
}

// Test cases
// Example 1
$nums1 = [1, 2, 3, 4, 5];
$k1 = 2;
echo "Output: " . maximumLength($nums1, $k1) . "\n"; // Output: 5

// Example 2
$nums2 = [1, 4, 2, 3, 1, 4];
$k2 = 3;
echo "Output: " . maximumLength($nums2, $k2) . "\n"; // Output: 4
?>

Explanation:

1. Initialization: The algorithm initializes the maximum length $ans to 0.
2. Iterate Over Values: For each possible value val from 0 to k-1, it initializes a dynamic programming array $dp of size k to store the maximum subsequence lengths ending with each residue.
3. Process Elements: For each element in the array, it computes the residue r of the element modulo k. The required previous residue s is calculated as (k + val - r) % k.
4. Update DP Array: The candidate length for the current element is set to 1 (if starting a new subsequence) or $dp[$s] + 1 (if extending an existing subsequence). The $dp array is updated if the candidate length exceeds the current value for residue r.
5. Track Maximum Length: The maximum length encountered during the processing is stored in $ans.
6. Return Result: After processing all elements and all values of val, the algorithm returns the maximum valid subsequence length found.

This approach efficiently checks all possible valid subsequences by leveraging dynamic programming and modular arithmetic, ensuring optimal performance even for the upper constraint limits.

[topugit]

Thanks for solving the problem of "Find the Maximum Length of Valid Subsequence II"

[mah-shamim]

Thanks