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#
Use a dictionary to store the best result for each (last value, modulo) pair.
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.
Always allow starting a new subsequence with the current number and undefined modulo.
The answer is the maximum length for any state.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
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