3201: Find-the-Maximum-Length-of-Valid-Subsequence-I
Medium
table of contents
You can simply reword the question. Realise that to have a subsequence where adjacent elements sum:
- to an even value, it implies that they are all of the same parity
- to an odd value, it implies that they are of alternating parity
Simply just iterate through nums and keep track of
three things:
Finally, simply return the maximum value out of them three.
code
class Solution {
public:
int maximumLength(vector<int>& nums) {
int parityCount[2] = {0};
int alternatingLength = 1;
int alternatingParity = nums[0]%2;
++parityCount[nums[0]%2];
for (int i = 1; i < nums.size(); ++i) {
++parityCount[nums[i]%2];
if (nums[i]%2 != alternatingParity) {
alternatingParity = nums[i]%2;
++alternatingLength;
}
}
return max(alternatingLength, max(parityCount));
}
};