3491. Find The Maximum Length Of Valid Subsequence Ii¶

Difficulty: Medium

LeetCode Problem View on GitHub

3491. Find the Maximum Length of Valid Subsequence II

Medium

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 <= 10³
1 <= nums[i] <= 10⁷
1 <= k <= 10³

Solution¶

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

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here