Solution-Find the Maximum Length of Valid Subsequence I

According to the definition of a valid subsequence, we can observe that all elements at odd indices in the subsequence must have the same parity, and all elements at even indices must also have the same parity. Therefore, there are a total of four possible parity patterns for the subsequence:

1. All elements are even.
2. All elements are odd.
3. Elements at odd indices are odd, and elements at even indices are even.
4. Elements at odd indices are even, and elements at even indices are odd.

We can enumerate these four possibilities. For each one, we traverse the entire nums array and calculate the maximum length of a subsequence that fits the chosen pattern. While traversing, if the current number satisfies the required parity based on its position in the subsequence, we greedily increase the length by 1.
Finally, we return the maximum subsequence length across all possibilities.

###cpp

class Solution {
public:
   int maximumLength(vector<int>& nums) {
       int res = 0;
       vector<vector<int>> patterns = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
       for (auto& pattern : patterns) {
           int cnt = 0;
           for (int num : nums) {
               if (num % 2 == pattern[cnt % 2]) {
                   cnt++;
               }
           }
           res = max(res, cnt);
       }
       return res;
   }
};

###java

class Solution {

   public int maximumLength(int[] nums) {
       int res = 0;
       int[][] patterns = { { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } };
       for (int[] pattern : patterns) {
           int cnt = 0;
           for (int num : nums) {
               if (num % 2 == pattern[cnt % 2]) {
                   cnt++;
               }
           }
           res = Math.max(res, cnt);
       }
       return res;
   }
}

###c

int maximumLength(int* nums, int numsSize) {
   int res = 0;
   int patterns[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
   for (int i = 0; i < 4; i++) {
       int cnt = 0;
       for (int j = 0; j < numsSize; j++) {
           if (nums[j] % 2 == patterns[i][cnt % 2]) {
               cnt++;
           }
       }
       if (cnt > res) {
           res = cnt;
       }
   }
   return res;
}

###csharp

public class Solution {
   public int MaximumLength(int[] nums) {
       int res = 0;
       int[,] patterns =
           new int[4, 2] { { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } };
       for (int i = 0; i < 4; i++) {
           int cnt = 0;
           foreach (int num in nums) {
               if (num % 2 == patterns[i, cnt % 2]) {
                   cnt++;
               }
           }
           res = Math.Max(res, cnt);
       }
       return res;
   }
}

###javascript

var maximumLength = function (nums) {
   let res = 0;
   const patterns = [
       [0, 0],
       [0, 1],
       [1, 0],
       [1, 1],
   ];
   for (const pattern of patterns) {
       let cnt = 0;
       for (const num of nums) {
           if (num % 2 === pattern[cnt % 2]) {
               cnt++;
           }
       }
       res = Math.max(res, cnt);
   }
   return res;
};

###golang

func maximumLength(nums []int) int {
   res := 0
   patterns := [][]int{{0, 0}, {0, 1}, {1, 0}, {1, 1}}
   for _, pattern := range patterns {
   cnt := 0
   for _, num := range nums {
   if num%2 == pattern[cnt%2] {
   cnt++
   }
   }
   res = max(res, cnt)
   }
   return res
}

###python3

class Solution:
   def maximumLength(self, nums: List[int]) -> int:
       res = 0
       for pattern in [[0, 0], [0, 1], [1, 0], [1, 1]]:
           cnt = 0
           for num in nums:
               if num % 2 == pattern[cnt % 2]:
                   cnt += 1
           res = max(res, cnt)
       return res

###rust

impl Solution {
   pub fn maximum_length(nums: Vec<i32>) -> i32 {
       let mut res = 0;
       let patterns = vec![vec![0, 0], vec![0, 1], vec![1, 0], vec![1, 1]];
       for pattern in patterns {
           let mut cnt = 0;
           for num in &nums {
               if num % 2 == pattern[cnt % 2] {
                   cnt += 1;
               }
           }
           res = res.max(cnt);
       }
       res as i32
   }
}

###typescript

function maximumLength(nums: number[]): number {
   let res = 0;
   const patterns = [
       [0, 0],
       [0, 1],
       [1, 0],
       [1, 1],
   ] as const;
   for (const pattern of patterns) {
       let cnt = 0;
       for (const num of nums) {
           if (num % 2 === pattern[cnt % 2]) {
               cnt++;
           }
       }
       res = Math.max(res, cnt);
   }
   return res;
}

Let $n$ be the length of the array $\textit{nums}$.

• Time complexity: $O(n)$. We only need to traverse the array once.
• Space complexity: $O(1)$.

Generated by RSStT. The copyright belongs to the original author.

Source