3202. Find the Maximum Length of Valid Subsequence II

Difficulty: Medium

Topics:Array,Dynamic Programming

You are given an integer arraynums and apositive integerk.

A subsequence¹sub ofnums with lengthx is calledvalid if it satisfies:

• (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.

Returnthe length of thelongest valid subsequence ofnums.

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 thek possible values. Let it beval.
2. Letdp[i] store the maximum length of a subsequence with its last elementx such thatx % k == i.
3. Answer for a subsequence ending at indexy isdp[(k + val - (y % k)) % k] + 1.

Solution:

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 integerk.

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 valueval. This condition implies that the residues of the elements in the subsequence must alternate between two residuesr₀ andr₁ such that(r₀ + r₁) % k = val. Additionally, the subsequence can consist of elements with a single residuer₀ where(2 x r₀) % k = val.

2. Dynamic Programming Setup: For each possible valueval (from 0 tok-1), we use a dynamic programming arraydp wheredp[r] stores the maximum length of a valid subsequence ending with an element whose residue isr under the currentval.

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

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

5. Result Extraction: After processing all elements for all possible values ofval, 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 */functionmaximumLength($nums,$k){........./**     * go to ./solution.php     */}// 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 valueval from 0 tok-1, it initializes a dynamic programming array$dp of sizek to store the maximum subsequence lengths ending with each residue.
3. Process Elements: For each element in the array, it computes the residuer of the element modulok. The required previous residues 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 residuer.
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 ofval, 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.

Contact Links

If you found this series helpful, please consider giving therepository a star on GitHub or sharing the post on your favorite social networks 😍.Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

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