Skip to content

3202. Find the Maximum Length of Valid Subsequence II

Description

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

Solutions

Solution 1: Dynamic Programming

Thinking

The modulus is now an arbitrary \(k\le 10^3\) with \(n\le 10^3\). Subsequence enumeration is still infeasible, but equal adjacent sums still force odd positions to share one residue and even positions another, so the state remains the last two residues.

\(n\times k\le 10^6\) lets us, for each value, enumerate the target pair-sum \(j\in[0,k)\), recover \(y=(j-x+k)\bmod k\), and set \(f[x][y]=f[y][x]+1\). The recurrence is the same as in the \(k=2\) case; only the table side length changes.

Based on the problem description, we know that for a subsequence \(a_1, a_2, a_3, \cdots, a_x\), if it satisfies \((a_1 + a_2) \bmod k = (a_2 + a_3) \bmod k\), then \(a_1 \bmod k = a_3 \bmod k\). This means that the result of taking modulo \(k\) for all odd-indexed elements is the same, and the result for all even-indexed elements is the same as well.

We can solve this problem using dynamic programming. Define the state \(f[x][y]\) as the length of the longest valid subsequence where the last element modulo \(k\) equals \(x\), and the second to last element modulo \(k\) equals \(y\). Initially, \(f[x][y] = 0\).

Iterate through the array \(nums\), and for each number \(x\), we get \(x = x \bmod k\). Then, we can enumerate the sequences where two consecutive numbers modulo \(j\) yield the same result, where \(j \in [0, k)\). Thus, the previous number modulo \(k\) would be \(y = (j - x + k) \bmod k\). At this point, \(f[x][y] = f[y][x] + 1\).

The answer is the maximum value among all \(f[x][y]\).

The time complexity is \(O(n \times k)\), and the space complexity is \(O(k^2)\). Here, \(n\) is the length of the array \(\textit{nums}\), and \(k\) is the given positive integer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [[0] * k for _ in range(k)]
        ans = 0
        for x in nums:
            x %= k
            for j in range(k):
                y = (j - x + k) % k
                f[x][y] = f[y][x] + 1
                ans = max(ans, f[x][y])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int maximumLength(int[] nums, int k) {
        int[][] f = new int[k][k];
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = Math.max(ans, f[x][y]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int f[k][k];
        memset(f, 0, sizeof(f));
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = max(ans, f[x][y]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maximumLength(nums []int, k int) (ans int) {
    f := make([][]int, k)
    for i := range f {
        f[i] = make([]int, k)
    }
    for _, x := range nums {
        x %= k
        for j := 0; j < k; j++ {
            y := (j - x + k) % k
            f[x][y] = f[y][x] + 1
            ans = max(ans, f[x][y])
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maximumLength(nums: number[], k: number): number {
    const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0));
    let ans: number = 0;
    for (let x of nums) {
        x %= k;
        for (let j = 0; j < k; ++j) {
            const y = (j - x + k) % k;
            f[x][y] = f[y][x] + 1;
            ans = Math.max(ans, f[x][y]);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut f = vec![vec![0; k]; k];
        let mut ans = 0;
        for x in nums {
            let x = (x % k as i32) as usize;
            for j in 0..k {
                let y = (j + k - x) % k;
                f[x][y] = f[y][x] + 1;
                ans = ans.max(f[x][y]);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
    public int MaximumLength(int[] nums, int k) {
        int[,] f = new int[k, k];
        int ans = 0;
        foreach (int num in nums) {
            int x = num % k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x, y] = f[y, x] + 1;
                ans = Math.Max(ans, f[x, y]);
            }
        }
        return ans;
    }
}

Comments