🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve the problem of finding the longest valid subsequence where consecutive pairs have equal sums modulo k
, we can utilize a dynamic programming approach. The key insight is to maintain a mapping of remainder values modulo k
to the length of subsequences that end with each remainder.
Approach
- Initialization: Initialize a dictionary or array
remainder_to_length
to keep track of the maximum length of subsequences that end with each remainder modulok
. - Iterate through
nums
: For each numbernum
innums
, calculate its remainder modulok
. - Update lengths: For each remainder, update
remainder_to_length
by considering addingnum
to subsequences ending with the previous remainder(curr_remainder + num) % k
. - Track maximum length: Maintain a variable
max_length
to store the maximum length found during the iteration. - Return result: After iterating through all numbers in
nums
,max_length
will contain the length of the longest valid subsequence.
Complexity
- Time Complexity: O(n), where n is the length of
nums
. We iterate throughnums
once and perform constant-time operations for each element. - Space Complexity: O(k), where k is the value of
k
. The space is primarily used to store mappings of remainders to lengths of subsequences, which can have up tok
entries.
The solution efficiently computes the length of the longest valid subsequence using dynamic programming and hashing, ensuring optimal performance.
Code Explanation
var maximumLength = function (nums, k) {
- Defines a function
maximumLength
that takes two parameters:nums
, an array of integers, andk
, a positive integer. The function aims to find the length of the longest valid subsequence where consecutive pairs have equal sums modulok
.
let dp = new Array(k * k).fill(0);
- Initializes an array
dp
of sizek * k
filled with zeros. This array will store the maximum lengths of subsequences that end with specific remainders modulok
.
var helper = (x, y) => x * k + y;
- Defines a helper function
helper
that calculates indices in thedp
array based on two remaindersx
andy
using the formulax * k + y
. This function simplifies accessing and updating elements in thedp
array based on remainders.
nums.forEach((num) => {
num %= k;
for (let i = 0; i < k; i++) {
if (dp[helper(num, i)] + 1 > dp[helper(i, num)]) {
dp[helper(i, num)] = dp[helper(num, i)] + 1;
}
}
});
- Iterates through each number
num
in thenums
array. For eachnum
, computes its remainder modulok
. - For each remainder
num % k
, iterates through all possible remaindersi
from 0 tok-1
. - Checks if adding
num
to the subsequence ending with remainderi
produces a longer valid subsequence than usingi
as the current remainder. - Updates the
dp
array with the new maximum length of subsequences if a longer valid subsequence is found.
return Math.max(...dp);
};
- Returns the maximum value found in the
dp
array usingMath.max(...dp)
, which represents the length of the longest valid subsequence found based on the conditions specified.
Code
C++
class Solution {
public:
int maximumLength(vector& nums, int k) {
vector dp(k * k, 0);
auto helper = [&](int x, int y, int k) {
return x * k + y;
};
for (int num : nums) {
num %= k;
for (int i = 0; i < k; i++) {
if (dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]) {
dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1;
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
Python
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
dp = [0] * (k * k)
def helper(x, y, k):
return x * k + y
for num in nums:
num %= k
for i in range(k):
if dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]:
dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1
return max(dp)
Java
class Solution {
public int maximumLength(int[] nums, int k) {
int[] dp = new int[k * k];
for (int num : nums) {
num %= k;
for (int i = 0; i < k; i++) {
if (dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]) {
dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1;
}
}
}
int max = 0;
for (int value : dp) {
max = Math.max(max, value);
}
return max;
}
private int helper(int x, int y, int k) {
return x * k + y;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumLength = function (nums, k) {
let dp = new Array(k * k).fill(0);
var helper = (x, y) => x * k + y;
nums.forEach((num) => {
num %= k;
for (let i = 0; i < k; i++) {
if (dp[helper(num, i)] + 1 > dp[helper(i, num)]) {
dp[helper(i, num)] = dp[helper(num, i)] + 1;
}
}
});
return Math.max(...dp);
};