[LeetCode] 3201. Find the Maximum Length of Valid Subsequence I

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 length of the longest valid subsequence 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.

Example 1:
Input: nums = [1,2,3,4]
Output: 4

Explanation:
The longest valid subsequence is [1, 2, 3, 4].

Example 2:
Input: nums = [1,2,1,1,2,1,2]
Output: 6

Explanation:
The longest valid subsequence is [1, 2, 1, 2, 1, 2].

Example 3:
Input: nums = [1,3]
Output: 2

Explanation:
The longest valid subsequence is [1, 3].

Constraints:
2 <= nums.length <= 2 * 105
1 <= nums[i] <= 107

找出有效子序列的最大长度 I。

给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == … == (sub[x - 2] + sub[x - 1]) % 2
返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

思路

思路是贪心。虽然这道题要找的是最长的子序列，意味着可以对 input 数组排序，但是排序对题目起不到作用。

注意有效子序列的定义，两个数的和的奇偶性是相同的。也就是说，所有的奇数可以组成有效子序列，所有的偶数也可以组成有效子序列，同时所有奇偶相间的子数组也可以组成合法的子序列。那么我们可以找这三种情况的最大值即可。注意代码中最后为什么是 t + 1，因为最后一个元素也要算上。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int maximumLength(int[] nums) {
        int n = nums.length;
        int odd = 0;
        int even = 0;
        int t = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] % 2 == 0) {
                even++;
            } else {
                odd++;
            }
            if (nums[i] % 2 != nums[i + 1] % 2) {
                t++;
            }
        }
        if (nums[n - 1] % 2 == 0) {
            even++;
        } else {
            odd++;
        }
        return Math.max(t + 1, Math.max(even, odd));
    }
}