What is the primary pattern used to solve the "Find the Maximum Length of Valid Subsequence I" problem?

The primary pattern is state transition dynamic programming, where you track subsequences based on parity (odd/even) and possible alternating patterns.

What are the possible patterns for a valid subsequence?

The valid subsequences can either be all even elements, all odd elements, alternating even-odd elements, or alternating odd-even elements.

How does the dynamic programming approach work for this problem?

The dynamic programming approach works by maintaining the length of valid subsequences for odd and even elements, and updating these lengths as you move through the array.

What is the time complexity of solving this problem?

The time complexity is O(n) because we traverse the array only once, making state transitions based on each element.

Can a greedy approach work for this problem?

Yes, a greedy approach can be used to find the longest subsequence by alternating between odd and even elements, or focusing on subsequences with all odd or all even numbers.

#3201

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 nums 。 nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为有效子序列： (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2 返回…

数组动态规划

题目描述

给你一个整数数组 nums。

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

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

返回 nums 的 最长的有效子序列 的长度。

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

示例 1：

输入： nums = [1,2,3,4]

输出： 4

解释：

最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输入： nums = [1,2,1,1,2,1,2]

输出： 6

解释：

最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输入： nums = [1,3]

输出： 2

解释：

最长的有效子序列是 [1, 3]。

提示：

2 <= nums.length <= 2 * 10⁵
1 <= nums[i] <= 10⁷

lightbulb

解题思路

方法一：动态规划

我们令 $k = 2$ 。

根据题目描述，我们可以得知，对于子序列 $a_1, a_2, a_3, \cdots, a_x$ ，如果满足 $(a_1 + a_2) \bmod k = (a_2 + a_3) \bmod k$ 。那么 $a_1 \bmod k = a_3 \bmod k$ 。也即是说，所有奇数项元素对 $k$ 取模的结果相同，所有偶数项元素对 $k$ 取模的结果相同。

我们可以使用动态规划的方法解决这个问题。定义状态 $f[x][y]$ 表示最后一项对 $k$ 取模为 $x$ ，倒数第二项对 $k$ 取模为 $y$ 的最长有效子序列的长度。初始时 $f[x][y] = 0$ 。

遍历数组 $nums$ ，对于每一个数 $x$ ，我们得到 $x = x \bmod k$ 。然后我们可以枚举序列连续两个数对 $j$ 取模结果相同，其中 $j \in [0, k)$ 。那么 $x$ 的前一个数对 $k$ 取模结果为 $y = (j - x + k) \bmod k$ 。此时 $f[x][y] = f[y][x] + 1$ 。

答案为所有 $f[x][y]$ 中的最大值。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(k^2)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度，而 $k=2$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        k = 2
        f = [[0] * k for _ in range(k)]
        ans = 0
        for x in nums:
            x %= k
            for j in range(k):
                y = (j - x + k) % k
                f[x][y] = f[y][x] + 1
                ans = max(ans, f[x][y])
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with dynamic programming and state transitions.
question_mark
Check if the candidate understands subsequence patterns and edge cases.
question_mark
Observe how the candidate handles different subsequences' parity and alternating patterns.

warning

常见陷阱

外企场景

error
Confusing the subsequence with a subarray, which requires contiguous elements.
error
Forgetting to properly alternate between odd and even elements in valid subsequences.
error
Not properly handling arrays with mixed parity that require alternating patterns.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the case when all numbers are the same.
arrow_right_alt
What if the array contains only even or only odd numbers?
arrow_right_alt
How does the solution scale with the maximum array size?

help

常见问题

外企场景

继续练习

#3202 找出有效子序列的最大长度 II #3196 最大化子数组的总成本 #3193 统计逆序对的数目