aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-15 23:32:54 -0600
committerJack Sangdahl <[email protected]>2025-07-15 23:32:54 -0600
commit2c28784a21926f822308a17383d812d12c5ce206 (patch)
tree732422715dc7fb1be9623590f50a02467b8f3a5f
parenta18969f1aacb4e46ea00cd1415ae349433fb1b70 (diff)
downloadleetcode-2c28784a21926f822308a17383d812d12c5ce206.tar.gz
leetcode-2c28784a21926f822308a17383d812d12c5ce206.zip
3201. find the maximum length of valid subsequence 1
-rw-r--r--find_max_len_valid_subseq1.c53
-rw-r--r--find_max_len_valid_subseq1.py28
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]))