🎨Now live: Try our Free AI Image Generation Feature

Intuition
To find the longest valid subsequence where the sum of every adjacent pair modulo 2 is the same, we can leverage properties of even and odd numbers. Specifically, sequences of even or odd numbers will satisfy the condition trivially.
Approach
- Counting Evens and Odds: First, count the number of even and odd numbers in the array
nums
. - Longest Subsequence Calculation: The longest valid subsequence can be formed by selecting either all even numbers or all odd numbers. Hence, the length of the longest valid subsequence will be the maximum of the count of even numbers or the count of odd numbers.
Complexity
- Time Complexity: O(n), where n is the length of the array
nums
. We only need to iterate through the array once to count evens and odds. - Space Complexity: O(1). We are using a constant amount of extra space for storing counts of even and odd numbers.
Code Explanation
Initialization
let a = 0,
b = 0,
c = 0,
d = 0;
- Initializes four variables:
-
a
: Counter for even numbers. -b
: Counter for odd numbers. -c
: Length of the valid subsequence ending with the last even number encountered. -d
: Length of the valid subsequence ending with the last odd number encountered.
Loop through Array
for (let num of nums) {
- Begins a
for ... of
loop to iterate through each elementnum
in the arraynums
.
Conditional Logic
if (num % 2 === 0) {
a++;
c = d + 1;
} else {
b++;
d = c + 1;
}
- Checks if the current
num
is even (num % 2 === 0
): - Incrementsa
(count of even numbers). - Updatesc
tod + 1
(length of the subsequence ending with the current even number). - If
num
is odd: - Incrementsb
(count of odd numbers). - Updatesd
toc + 1
(length of the subsequence ending with the current odd number). - Ends the
for ... of
loop after iterating through all elements ofnums
.
Return Statement
return Math.max(a, b, c, d);
- Calculates the maximum length among
a
,b
,c
, andd
usingMath.max
. - Returns this maximum length, which represents the length of the longest valid subsequence according to the given conditions.
Code
C++
class Solution {
public:
int maximumLength(vector& nums) {
int a = 0, b = 0, c = 0, d = 0;
for (int num : nums) {
if (num % 2 == 0) {
a++;
c = d + 1;
} else {
b++;
d = c + 1;
}
}
return max({a, b, c, d});
}
};
Python
class Solution:
def maximumLength(self, nums: List[int]) -> int:
a, b, c, d = 0, 0, 0, 0
for num in nums:
if num % 2 == 0:
a += 1
c = d + 1
else:
b += 1
d = c + 1
return max(a, b, c, d)
Java
class Solution {
public int maximumLength(int[] nums) {
int a = 0, b = 0, c = 0, d = 0;
for (int num : nums) {
if (num % 2 == 0) {
a++;
c = d + 1;
} else {
b++;
d = c + 1;
}
}
return Math.max(Math.max(a, b), Math.max(c, d));
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maximumLength = function(nums) {
let a = 0, b = 0, c = 0, d = 0;
for (let num of nums) {
if (num % 2 === 0) {
a++;
c = d + 1;
} else {
b++;
d = c + 1;
}
}
return Math.max(a, b, c, d);
};