leetcode

commit eea791708232d7e8b1db4f2e257e814e8117f580
parent 2d3548496b062725d6b40ae2a1941a8c44d1213c
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 16 Jul 2025 10:32:26 -0500

Completed find the maximum length of valid subsequence i

Diffstat:
A
find-the-maximum-length-of-valid-subsequence-i/find-the-maximum-length-of-valid-subsequence-iV1.py
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 54 insertions(+), 0 deletions(-)
diff --git a/find-the-maximum-length-of-valid-subsequence-i/find-the-maximum-length-of-valid-subsequence-iV1.py b/find-the-maximum-length-of-valid-subsequence-i/find-the-maximum-length-of-valid-subsequence-iV1.py
@@ -0,0 +1,54 @@
+# subsequence is an ordered selection
+# of elements in nums that can be derived
+# by some or no elements
+
+# (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2.
+
+# two options:
+# sub[0] + sub[1] % 2 == 0
+# sub[0] + sub[1] % 2 == 1
+
+# assume sub[0] + sub[1] % 2 == 0
+# given this, make optimal selections
+# assume sub[0] + sub[1] % 2 == 1
+# given this, make optimal selections
+# return len(sub)
+
+# how to make optimal selections?
+# 1) brute force - UNREASONABLE
+# 2) try all elements odd. try all elements even. try all even then odd. try all odd then even
+
+
+class Solution:
+    def maximumLength(self, nums: List[int]) -> int:
+
+        odds = longest_subsequence(1, 1, nums)
+        evens = longest_subsequence(0, 0, nums)
+
+        opp1 = longest_subsequence(1, 0, nums)
+        opp2 = longest_subsequence(0, 1, nums)
+
+        return max(evens, odds, opp1, opp2)
+
+
+# pass in the first lower % 2 value, first upper % 2 value, and nums
+def longest_subsequence(lower_mod, upper_mod, nums):
+
+    length = 0
+    lower_bound = -1
+    current_mod = lower_mod
+
+    while lower_bound < len(nums):
+        before = lower_bound
+        for index in range(lower_bound + 1, len(nums)):
+            if nums[index] % 2 == current_mod:
+                length += 1
+                lower_bound = index
+                if current_mod == lower_mod:
+                    current_mod = upper_mod
+                else:
+                    current_mod = lower_mod
+
+        if before == lower_bound:
+            lower_bound = len(nums)
+    return length