3201. Find the Maximum Length of Valid Subsequence II

Description

You are given an integer array nums and a positive integer k.

A 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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(nk)
• Space complexity: O(k²)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const maximumLength = function (nums, k) {
  const dp = Array.from({ length: k }, () => new Array(k).fill(0));
  let result = 0;

  for (const num of nums) {
    const mod = num % k;

    for (let prev = 0; prev < k; prev++) {
      dp[mod][prev] = dp[prev][mod] + 1;
      result = Math.max(dp[mod][prev], result);
    }
  }

  return result;
};