[LeetCode] Find the Maximum Length of Valid Subsequence I

3201. Find the Maximum Length of Valid Subsequence I

You are given an integer array nums.

A subsequence sub of nums with length x is called valid if it satisfies:

  • (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2.

Return the length of the longest valid subsequence of nums.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
int helper(vector<int>& A, int a, int b) {
int res = 0;
for(int i = 0; i < A.size(); i++) {
if(A[i] % 2 == a) {
res++;
swap(a,b);
}
}
return res;
}
public:
int maximumLength(vector<int>& A) {
int res = 0;
for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) {
res = max(res, helper(A,i,j));
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/06/30/PS/LeetCode/find-the-maximum-length-of-valid-subsequence-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.