Find the Maximum Length of Valid Subsequence II
Source: leetcode
Difficulty: Medium
Tags: 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`




C++ solution:
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        // Step 1: Collect positions of each number
        vector<vector<int>> positions(k);
        for (int i = 0; i < nums.size(); ++i)
            positions[nums[i] % k].push_back(i);

        sort(begin(positions), end(positions), [](const auto &a, const auto &b){ return a.size() > b.size(); });
        int maxLength = max(2, (int)positions[0].size());

        // Step 3: Find the longest interweaved subsequence for each pair of numbers
        for (int i = 0; i < positions.size(); ++i) {
            for (int j = i + 1; j < positions.size() && positions[i].size() + positions[j].size() > maxLength; ++j) {
                int length_ij = (positions[i][0] < positions[j][0]) + (positions[i].back() < positions[j].back());
                for (int k = 0, l = 0; k < positions[i].size() && l < positions[j].size(); ++k) {
                    if (positions[j][l] < positions[i][k])
                        length_ij += 2;
                    while (l < positions[j].size() && positions[j][l] < positions[i][k])
                        ++l;
                }
                maxLength = max(maxLength, length_ij);
            }
        }
        return maxLength;
    } 
};

Go solution:
func maximumLength(nums []int, k int) int {
	n := len(nums)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, k)
	}

	res := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			mod := (nums[i] + nums[j]) % k
			length := 1 + calc(j, mod, &dp, nums, k)
			if length > res {
				res = length
			}
		}
	}

	return res
}

func calc(i, rem int, dp *[][]int, nums []int, k int) int {
	if (*dp)[i][rem] != 0 {
		return (*dp)[i][rem]
	}

	result := 1
	for j := i + 1; j < len(nums); j++ {
		if (nums[j] + nums[i]) % k == rem {
			result += calc(j, rem, dp, nums, k)
			break
		}
	}
	(*dp)[i][rem] = result
	return result
}

Java solution:
class Solution {
    public int maximumLength(int[] nums, int k) {
        int dp[][] = new int[k][k], max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < k; j++) {
                max = Math.max(max, dp[nums[i] % k][j] = dp[j][nums[i] % k] + 1);
            }
        }
        return max;
    }
}

JavaScript solution:
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumLength = function(nums, k) {
    let dp = Array.from({ length: k }, () => Array(k).fill(0));
    let maxLen = 0;
    
    nums.forEach(num => {
        let remainder = num % k;
        for (let j = 0; j < k; j++) {
            dp[remainder][j] = Math.max(dp[remainder][j], dp[j][remainder] + 1);
            maxLen = Math.max(maxLen, dp[remainder][j]);
        }
    });
    
    return maxLen;
};

Python solution:
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        nums = [num % k for num in nums]
        def check(a, b):
            alternating = (num for num in nums if num == a or num == b)
            return 1 + sum([1 for a, b in pairwise(alternating) if a != b])
        
        counts = sorted([(count, val) for val, count in Counter(nums).items()], reverse=True)
        best = counts[0][0]
        for i in range(len(counts)-1):
            countA, a = counts[i]
            for j in range(i+1, len(counts)):
                countB, b = counts[j]
                if countA + countB <= best:
                    break
                best = max(best, check(a, b))
        return best

Ruby solution:
def maximum_length(nums, k)
  mod_nums = nums.map { |num| num % k }
  counts = Hash.new(0)
  mod_nums.each { |r| counts[r] += 1 }
  sorted_counts = counts.to_a.sort_by { |r, cnt| -cnt }

  best = sorted_counts.any? ? sorted_counts[0][1] : 0

  (0...sorted_counts.size).each do |i|
    a, cnt_a = sorted_counts[i]
    ((i + 1)...sorted_counts.size).each do |j|
      b, cnt_b = sorted_counts[j]
      if cnt_a + cnt_b <= best
        break
      end
      current_max = check_alternating(mod_nums, a, b)
      best = [best, current_max].max
    end
  end

  best
end

def check_alternating(mod_nums, a, b)
  a_len = 0
  b_len = 0
  mod_nums.each do |r|
    if r == a
      new_a = [a_len, b_len + 1].max
      a_len = new_a
    elsif r == b
      new_b = [b_len, a_len + 1].max
      b_len = new_b
    end
  end
  [a_len, b_len].max
end