find-the-maximum-length-of-valid-subsequence-iV1.py (1563B)
1 # subsequence is an ordered selection 2 # of elements in nums that can be derived 3 # by some or no elements 4 5 # (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2. 6 7 # two options: 8 # sub[0] + sub[1] % 2 == 0 9 # sub[0] + sub[1] % 2 == 1 10 11 # assume sub[0] + sub[1] % 2 == 0 12 # given this, make optimal selections 13 # assume sub[0] + sub[1] % 2 == 1 14 # given this, make optimal selections 15 # return len(sub) 16 17 # how to make optimal selections? 18 # 1) brute force - UNREASONABLE 19 # 2) try all elements odd. try all elements even. try all even then odd. try all odd then even 20 21 22 class Solution: 23 def maximumLength(self, nums: List[int]) -> int: 24 25 odds = longest_subsequence(1, 1, nums) 26 evens = longest_subsequence(0, 0, nums) 27 28 opp1 = longest_subsequence(1, 0, nums) 29 opp2 = longest_subsequence(0, 1, nums) 30 31 return max(evens, odds, opp1, opp2) 32 33 34 # pass in the first lower % 2 value, first upper % 2 value, and nums 35 def longest_subsequence(lower_mod, upper_mod, nums): 36 37 length = 0 38 lower_bound = -1 39 current_mod = lower_mod 40 41 while lower_bound < len(nums): 42 before = lower_bound 43 for index in range(lower_bound + 1, len(nums)): 44 if nums[index] % 2 == current_mod: 45 length += 1 46 lower_bound = index 47 if current_mod == lower_mod: 48 current_mod = upper_mod 49 else: 50 current_mod = lower_mod 51 52 if before == lower_bound: 53 lower_bound = len(nums) 54 return length