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

A valid subsequence requires that the value (sub[i] + sub[i+1]) % k is the same for all consecutive pairs. We can use dynamic programming to track, for each possible modulo value, the longest subsequence ending with a given last value and modulo.

Approach

  1. Use a dictionary to store the best result for each (last value, modulo) pair.
  2. For each number in nums, for each existing state, try to extend the subsequence:
    • Compute the new modulo as (last + x) % k.
    • Only keep the best length for each (value, modulo) pair.
  3. Always allow starting a new subsequence with the current number and undefined modulo.
  4. The answer is the maximum length for any state.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int longestValidSubsequence(vector<int>& nums, int k) {
        unordered_map<long long, int> dp; // key: (val<<8)|mod, value: max len
        int ans = 1;
        for(int x : nums) {
            unordered_map<long long, int> ndp;
            ndp[(long long(x)<<8)|255] = 1; // 255 as undefined mod
            for(auto& [key, l] : dp) {
                int v = key>>8, m = key&255;
                int nm = m==255 ? 255 : (v+x)%k;
                if(m==255) {
                    ndp[(long long(x)<<8)|255] = max(ndp[(long long(x)<<8)|255], 1);
                } else {
                    if((v+x)%k == m) {
                        long long nk = (long long(x)<<8)|m;
                        ndp[nk] = max(ndp[nk], l+1);
                        ans = max(ans, l+1);
                    }
                }
            }
            dp = ndp;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func longestValidSubsequence(nums []int, k int) int {
    dp := map[[2]int]int{} // [val, mod] -> max len
    ans := 1
    for _, x := range nums {
        ndp := map[[2]int]int{}
        ndp[[2]int{x, -1}] = 1
        for key, l := range dp {
            v, m := key[0], key[1]
            if m == -1 {
                ndp[[2]int{x, -1}] = 1
            } else if (v+x)%k == m {
                nk := [2]int{x, m}
                if ndp[nk] < l+1 { ndp[nk] = l+1 }
                if ans < l+1 { ans = l+1 }
            }
        }
        dp = ndp
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestValidSubsequence(int[] nums, int k) {
        Map<Long, Integer> dp = new HashMap<>();
        int ans = 1;
        for(int x : nums) {
            Map<Long, Integer> ndp = new HashMap<>();
            ndp.put(((long)x<<8)|255L, 1);
            for(var e : dp.entrySet()) {
                int v = (int)(e.getKey()>>8), m = (int)(e.getKey()&255);
                if(m==255) {
                    ndp.put(((long)x<<8)|255L, 1);
                } else if((v+x)%k==m) {
                    long nk = ((long)x<<8)|m;
                    ndp.put(nk, Math.max(ndp.getOrDefault(nk, 0), e.getValue()+1));
                    ans = Math.max(ans, e.getValue()+1);
                }
            }
            dp = ndp;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    fun longestValidSubsequence(nums: IntArray, k: Int): Int {
        var dp = mutableMapOf<Pair<Int,Int>,Int>()
        var ans = 1
        for (x in nums) {
            val ndp = mutableMapOf<Pair<Int,Int>,Int>()
            ndp[x to -1] = 1
            for ((key, l) in dp) {
                val (v, m) = key
                if (m == -1) {
                    ndp[x to -1] = 1
                } else if ((v+x)%k == m) {
                    val nk = x to m
                    ndp[nk] = maxOf(ndp.getOrDefault(nk,0), l+1)
                    ans = maxOf(ans, l+1)
                }
            }
            dp = ndp
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def longestValidSubsequence(self, nums: list[int], k: int) -> int:
        dp = dict()  # (val, mod) -> max len
        ans = 1
        for x in nums:
            ndp = dict()
            ndp[(x, None)] = 1
            for (v, m), l in dp.items():
                if m is None:
                    ndp[(x, None)] = 1
                elif (v + x) % k == m:
                    nk = (x, m)
                    ndp[nk] = max(ndp.get(nk, 0), l+1)
                    ans = max(ans, l+1)
            dp = ndp
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
use std::collections::HashMap;
impl Solution {
    pub fn longest_valid_subsequence(nums: Vec<i32>, k: i32) -> i32 {
        let mut dp = HashMap::new(); // (val, mod) -> max len
        let mut ans = 1;
        for &x in &nums {
            let mut ndp = HashMap::new();
            ndp.insert((x, None), 1);
            for (&(v, m), &l) in &dp {
                if m.is_none() {
                    ndp.insert((x, None), 1);
                } else if (v + x) % k == m.unwrap() {
                    let nk = (x, m);
                    ndp.insert(nk, ndp.get(&nk).copied().unwrap_or(0).max(l+1));
                    ans = ans.max(l+1);
                }
            }
            dp = ndp;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    longestValidSubsequence(nums: number[], k: number): number {
        let dp = new Map<string, number>();
        let ans = 1;
        for(const x of nums) {
            const ndp = new Map<string, number>();
            ndp.set(`${x},null`, 1);
            for(const [key, l] of dp.entries()) {
                const [v, m] = key.split(',');
                if(m==='null') {
                    ndp.set(`${x},null`, 1);
                } else if((+v + x) % k === +m) {
                    const nk = `${x},${m}`;
                    ndp.set(nk, Math.max(ndp.get(nk)||0, l+1));
                    ans = Math.max(ans, l+1);
                }
            }
            dp = ndp;
        }
        return ans;
    }
}

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