Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: nums = [1,2,3,4,5], k = 2

Output: 5

Explanation:

The longest valid subsequence is `[1, 2, 3, 4, 5]`.

Example 2

1
2
3
4
5
6
7
8


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^3
  • 1 <= nums[i] <= 10^7
  • 1 <= k <= 10^3

Solution

Method 1 – Dynamic Programming by Modulo State

Intuition

Suppose we want to build a valid subsequence where the value (A[i] + A[i+1]) % k remains constant for all consecutive elements. For each possible modulo value, we can keep track of the longest subsequence ending with a specific number and having that modulo.

Approach

Let DP[currNum][mod] represent the maximum length of a valid subsequence ending with currNum and having the required modulo mod for all consecutive pairs. For each number in the array, we try to extend all possible subsequences for every modulo value from 0 to k-1.

To include currNum in a subsequence with modulo mod, the previous number in the subsequence must satisfy (currNum + prevNum) % k = mod, which rearranges to prevNum = (mod - currNum + k) % k (ensuring non-negative results). Thus, for each mod, we look up the best subsequence ending with prevNum and update DP[currNum][mod] as max(DP[currNum][mod], 1 + DP[prevNum][mod]). We also consider starting a new subsequence with just currNum.

Finally, the answer is the largest value among all DP[num][mod] for all numbers and modulos.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        vector<vector<int>> dp(k, vector<int>(k, 0));
        int maxLen = 1;
        for (int num : nums) {
            int currRem = num % k;
            for (int mod = 0; mod < k; ++mod) {
                int prevRem = (mod - currRem + k) % k;
                dp[currRem][mod] = max(dp[currRem][mod], 1 + dp[prevRem][mod]);
                maxLen = max(maxLen, dp[currRem][mod]);
            }
        }
        return maxLen;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maximumLength(nums []int, k int) int {
    dp := make([][]int, k)
    for i := range dp {
        dp[i] = make([]int, k)
    }
    maxLen := 1
    for _, num := range nums {
        currRem := num % k
        for mod := 0; mod < k; mod++ {
            prevRem := (mod - currRem + k) % k
            if dp[currRem][mod] < 1+dp[prevRem][mod] {
                dp[currRem][mod] = 1 + dp[prevRem][mod]
            }
            if maxLen < dp[currRem][mod] {
                maxLen = dp[currRem][mod]
            }
        }
    }
    return maxLen
}
 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[][] dp = new int[k][k];
        int maxLen = 1;
        for (int num : nums) {
            int currRem = num % k;
            for (int mod = 0; mod < k; ++mod) {
                int prevRem = (mod - currRem + k) % k;
                dp[currRem][mod] = Math.max(dp[currRem][mod], 1 + dp[prevRem][mod]);
                maxLen = Math.max(maxLen, dp[currRem][mod]);
            }
        }
        return maxLen;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maximumLength(nums: IntArray, k: Int): Int {
        val dp = Array(k) { IntArray(k) }
        var maxLen = 1
        for (num in nums) {
            val currRem = num % k
            for (mod in 0 until k) {
                val prevRem = (mod - currRem + k) % k
                dp[currRem][mod] = maxOf(dp[currRem][mod], 1 + dp[prevRem][mod])
                maxLen = maxOf(maxLen, dp[currRem][mod])
            }
        }
        return maxLen
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = [[0] * k for _ in range(k)]
        max_len = 1
        for num in nums:
            curr_rem = num % k
            for mod in range(k):
                prev_rem = (mod - curr_rem + k) % k
                dp[curr_rem][mod] = max(dp[curr_rem][mod], 1 + dp[prev_rem][mod])
                max_len = max(max_len, dp[curr_rem][mod])
        return max_len
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut dp = vec![vec![0; k]; k];
        let mut max_len = 1;
        for &num in &nums {
            let curr_rem = (num % k as i32) as usize;
            for mod_ in 0..k {
                let prev_rem = (mod_ as i32 - curr_rem as i32 + k as i32) % k as i32;
                let prev_rem = prev_rem as usize;
                dp[curr_rem][mod_] = dp[curr_rem][mod_].max(1 + dp[prev_rem][mod_]);
                max_len = max_len.max(dp[curr_rem][mod_]);
            }
        }
        max_len
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumLength(nums: number[], k: number): number {
        const dp: number[][] = Array.from({ length: k }, () => Array(k).fill(0));
        let maxLen = 1;
        for (const num of nums) {
            const currRem = num % k;
            for (let mod = 0; mod < k; ++mod) {
                const prevRem = (mod - currRem + k) % k;
                dp[currRem][mod] = Math.max(dp[currRem][mod], 1 + dp[prevRem][mod]);
                maxLen = Math.max(maxLen, dp[currRem][mod]);
            }
        }
        return maxLen;
    }
}

Complexity

  • ⏰ Time complexity: O(n*k*U), where n is the length of nums and U is the number of unique values in nums.
  • 🧺 Space complexity: O(k*U), for the DP table