diff options
author | Jack Sangdahl <[email protected]> | 2025-07-15 23:32:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-15 23:32:54 -0600 |
commit | 2c28784a21926f822308a17383d812d12c5ce206 (patch) | |
tree | 732422715dc7fb1be9623590f50a02467b8f3a5f | |
parent | a18969f1aacb4e46ea00cd1415ae349433fb1b70 (diff) | |
download | leetcode-2c28784a21926f822308a17383d812d12c5ce206.tar.gz leetcode-2c28784a21926f822308a17383d812d12c5ce206.zip |
3201. find the maximum length of valid subsequence 1
-rw-r--r-- | find_max_len_valid_subseq1.c | 53 | ||||
-rw-r--r-- | find_max_len_valid_subseq1.py | 28 |
2 files changed, 81 insertions, 0 deletions
diff --git a/find_max_len_valid_subseq1.c b/find_max_len_valid_subseq1.c new file mode 100644 index 0000000..ecea5fc --- /dev/null +++ b/find_max_len_valid_subseq1.c @@ -0,0 +1,53 @@ +// 3201. Find the Maximum Length of Valid Subsequence I +#include "leetcode.h" + +/* + * 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 legnth of + * the longest valid subsequences 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. + */ + +int maximumLength(int *nums, int numsSize) { + int odd_start = 0, even_start = 0; + for (int i = 0; i < numsSize; i++) { + if (!(nums[odd_start] % 2) && (nums[i] % 2 == 1)) + odd_start = i; + if ((nums[even_start] % 2 == 1) && !(nums[i] % 2)) + even_start = i; + } + int odd_cnt1 = 1, odd_i1 = odd_start, odd_cnt2 = 1, odd_i2 = even_start; + int even_cnt1 = 1, even_i1 = odd_start, even_cnt2 = 1, even_i2 = even_start; + for (int i = odd_start + 1; i < numsSize; i++) { + if ((nums[odd_i1] + nums[i]) % 2 == 1) { + odd_i1 = i; + odd_cnt1++; + } + if (!((nums[even_i1] + nums[i]) % 2)) { + even_i1 = i; + even_cnt1++; + } + } + for (int i = even_start + 1; i < numsSize; i++) { + if ((nums[odd_i2] + nums[i]) % 2 == 1) { + odd_i2 = i; + odd_cnt2++; + } + if (!((nums[even_i2] + nums[i]) % 2)) { + even_i2 = i; + even_cnt2++; + } + } + int odd_max = fmax(odd_cnt1, odd_cnt2); + int even_max = fmaxl(even_cnt1, even_cnt2); + return fmax(odd_max, even_max); +} + +int main() { + int n1[] = {1, 2, 3, 4}, n2[] = {1, 2, 1, 1, 2, 1, 2}, n3[] = {1, 3}; + printf("%d\n", maximumLength(n1, ARRAY_SIZE(n1))); // expect: 4 + printf("%d\n", maximumLength(n2, ARRAY_SIZE(n2))); // expect: 6 + printf("%d\n", maximumLength(n3, ARRAY_SIZE(n3))); // expect: 2 +} diff --git a/find_max_len_valid_subseq1.py b/find_max_len_valid_subseq1.py new file mode 100644 index 0000000..f940e7f --- /dev/null +++ b/find_max_len_valid_subseq1.py @@ -0,0 +1,28 @@ +# 3201. Find the Maximum Length of Valid Subsequence I +from itertools import groupby + +""" +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 legnth of +the longest valid subsequences 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. +""" + + +class Solution(object): + def maximumLength(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + nums = [i % 2 for i in nums] + return max(nums.count(0), nums.count(1), len(list(groupby(nums)))) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumLength(nums=[1, 2, 3, 4])) + print(obj.maximumLength(nums=[1, 2, 1, 1, 2, 1, 2])) + print(obj.maximumLength(nums=[1, 3])) |