解法一
思路和算法
有效子序列满足子序列的任意相邻两项之和除以 $2$ 的余数相等，因此有效子序列中的元素奇偶性有如下四种情况。
对于每个有效子序列，在移除最后一个元素之后，剩余元素仍是有效子序列且有效子序列的元素奇偶性不变，因此可以使用动态规划计算最长有效子序列的长度。
用 $n$ 表示数组 $\textit{nums}$ 的长度。创建 $n \times 2 \times 2$ 的三维数组 $\textit{dp}$，其中 $\textit{dp}[i][0][0]$ 表示数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中的所有元素的奇偶性相同且都是偶数的最长有效子序列的长度，$\textit{dp}[i][0][1]$ 表示数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中的所有元素的奇偶性相同且都是奇数的最长有效子序列的长度， $\textit{dp}[i][1][0]$ 表示数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中的所有元素的奇偶性交替出现且末尾元素是偶数的最长有效子序列的长度，$\textit{dp}[i][1][1]$ 表示数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中的所有元素的奇偶性交替出现且末尾元素是奇数的最长有效子序列的长度。
当 $i = 0$ 时，数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中只有一个元素 $\textit{nums}[0]$，因此动态规划的边界情况如下。
-
当 $\textit{nums}[0]$ 是偶数时，$\textit{dp}[0][0][0] = \textit{dp}[0][1][0] = 1$，$\textit{dp}[0][0][1] = \textit{dp}[0][1][1] = 0$。
-
当 $\textit{nums}[0]$ 是奇数时，$\textit{dp}[0][0][0] = \textit{dp}[0][1][0] = 0$，$\textit{dp}[0][0][1] = \textit{dp}[0][1][1] = 1$。
当 $i > 0$ 时，需要根据 $\textit{nums}[i]$ 的奇偶性计算 $\textit{dp}[i][][]$ 的状态值。
-
当 $\textit{nums}[i]$ 是偶数时，如果 $\textit{nums}[i]$ 是有效子序列的末尾元素，则有效子序列的末尾元素是偶数，此时可以在所有元素都是偶数或者所有元素的奇偶性交替出现且末尾元素是奇数的有效子序列的后面添加 $\textit{nums}[i]$ 得到更长的有效子序列。
-
当 $\textit{nums}[i]$ 是奇数时，如果 $\textit{nums}[i]$ 是有效子序列的末尾元素，则有效子序列的末尾元素是奇数，此时可以在所有元素都是奇数或者所有元素的奇偶性交替出现且末尾元素是偶数的有效子序列的后面添加 $\textit{nums}[i]$ 得到更长的有效子序列。
因此动态规划的状态转移方程如下。
-
当 $\textit{nums}[i]$ 是偶数时，$\textit{dp}[i][0][0] = \textit{dp}[i - 1][0][0] + 1$，$\textit{dp}[i][0][1] = \textit{dp}[i - 1][0][1]$，$\textit{dp}[i][1][0] = \textit{dp}[i - 1][1][1] + 1$，$\textit{dp}[i][1][1] = \textit{dp}[i - 1][1][1]$。
-
当 $\textit{nums}[i]$ 是奇数时，$\textit{dp}[i][0][0] = \textit{dp}[i - 1][0][0]$，$\textit{dp}[i][0][1] = \textit{dp}[i - 1][0][1] + 1$，$\textit{dp}[i][1][0] = \textit{dp}[i - 1][1][0]$，$\textit{dp}[i][1][1] = \textit{dp}[i - 1][1][0] + 1$。
根据动态规划的状态转移方程，应从小到大遍历每个 $i$ 并计算 $\textit{dp}[i][][]$。计算所有的状态之后，$\textit{dp}[n - 1][][]$ 中的最大值即为最长有效子序列的长度。
上述做法的时间复杂度和空间复杂度都是 $O(n)$。
实现方面，由于 $\textit{dp}[i][][]$ 只取决于 $\textit{dp}[i - 1][][]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一个 $i$ 处的状态，将空间复杂度降到 $O(1)$。
代码
下面的代码为不优化空间的实现。
###Java
class Solution {
public int maximumLength(int[] nums) {
int n = nums.length;
int[][][] dp = new int[n][2][2];
dp[0][0][nums[0] % 2] = 1;
dp[0][1][nums[0] % 2] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] % 2 == 0) {
dp[i][0][0] = dp[i - 1][0][0] + 1;
dp[i][0][1] = dp[i - 1][0][1];
dp[i][1][0] = dp[i - 1][1][1] + 1;
dp[i][1][1] = dp[i - 1][1][1];
} else {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = dp[i - 1][0][1] + 1;
dp[i][1][0] = dp[i - 1][1][0];
dp[i][1][1] = dp[i - 1][1][0] + 1;
}
}
return Math.max(Math.max(dp[n - 1][0][0], dp[n - 1][0][1]), Math.max(dp[n - 1][1][0], dp[n - 1][1][1]));
}
}
###C#
public class Solution {
public int MaximumLength(int[] nums) {
int n = nums.Length;
int[][][] dp = new int[n][][];
for (int i = 0; i < n; i++) {
dp[i] = new int[2][];
for (int j = 0; j < 2; j++) {
dp[i][j] = new int[2];
}
}
dp[0][0][nums[0] % 2] = 1;
dp[0][1][nums[0] % 2] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] % 2 == 0) {
dp[i][0][0] = dp[i - 1][0][0] + 1;
dp[i][0][1] = dp[i - 1][0][1];
dp[i][1][0] = dp[i - 1][1][1] + 1;
dp[i][1][1] = dp[i - 1][1][1];
} else {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = dp[i - 1][0][1] + 1;
dp[i][1][0] = dp[i - 1][1][0];
dp[i][1][1] = dp[i - 1][1][0] + 1;
}
}
return Math.Max(Math.Max(dp[n - 1][0][0], dp[n - 1][0][1]), Math.Max(dp[n - 1][1][0], dp[n - 1][1][1]));
}
}
下面的代码为优化空间的实现。
###Java
class Solution {
public int maximumLength(int[] nums) {
int n = nums.length;
int[][] dp = new int[2][2];
dp[0][nums[0] % 2] = 1;
dp[1][nums[0] % 2] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] % 2 == 0) {
dp[0][0]++;
dp[1][0] = dp[1][1] + 1;
} else {
dp[0][1]++;
dp[1][1] = dp[1][0] + 1;
}
}
return Math.max(Math.max(dp[0][0], dp[0][1]), Math.max(dp[1][0], dp[1][1]));
}
}
###C#
public class Solution {
public int MaximumLength(int[] nums) {
int n = nums.Length;
int[][] dp = new int[2][];
for (int j = 0; j < 2; j++) {
dp[j] = new int[2];
}
dp[0][nums[0] % 2] = 1;
dp[1][nums[0] % 2] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] % 2 == 0) {
dp[0][0]++;
dp[1][0] = dp[1][1] + 1;
} else {
dp[0][1]++;
dp[1][1] = dp[1][0] + 1;
}
}
return Math.Max(Math.Max(dp[0][0], dp[0][1]), Math.Max(dp[1][0], dp[1][1]));
}
}
复杂度分析
解法二
思路和算法
考虑更一般的情况，子序列 $\textit{sub}$ 的任意相邻两项之和除以 $k$ 的余数相等。这道题为 $k = 2$ 的特例。
长度为 $x$ 的有效子序列 $\textit{sub}$ 满足对于任意 $1 \le i \le x - 2$ 都有 $(\textit{sub}[i - 1] + \textit{sub}[i]) \bmod k = (\textit{sub}[i] + \textit{sub}[i + 1]) \bmod k$，等价于 $(\textit{sub}[i - 1] + \textit{sub}[i] - \textit{sub}[i] - \textit{sub}[i + 1]) \bmod k = 0$，整理得 $(\textit{sub}[i - 1] - \textit{sub}[i + 1]) \bmod k = 0$，即 $\textit{sub}[i - 1] \bmod k = \textit{sub}[i + 1] \bmod k$。因此子序列 $\textit{sub}$ 满足子序列中的下标相差 $2$ 的两项除以 $k$ 的余数相等，进一步可以得到子序列 $\textit{sub}$ 满足所有偶数下标项除以 $k$ 的余数相等且所有奇数下标项除以 $k$ 的余数相等。
为了计算最长有效子序列的长度，对于所有满足 $0 \le i, j < k$ 的整数 $i$ 和 $j$ 需要计算最后两项除以 $k$ 的余数分别是 $i$ 和 $j$ 的子序列的最大长度。
创建 $k \times k$ 的二维数组 $\textit{dp}$，其中 $\textit{dp}[i][j]$ 表示最后两项除以 $k$ 的余数分别是 $i$ 和 $j$ 的子序列的最大长度。
动态规划的边界情况是：如果当前没有最后两项除以 $k$ 的余数分别是 $i$ 和 $j$ 的子序列，则 $\textit{dp}[i][j] = 0$。初始时，$\textit{dp}$ 中的所有状态值都是 $0$。
遍历数组 $\textit{nums}$，对于遍历到的每个元素 $\textit{num}$，执行如下操作。
-
计算当前余数 $\textit{curr} = \textit{num} \bmod k$。
-
遍历 $0 \le \textit{prev} < k$ 的每个余数 $\textit{prev}$，为了得到最后两项除以 $k$ 的余数分别是 $\textit{prev}$ 和 $\textit{curr}$ 的最长有效子序列，需要首先得到最后两项除以 $k$ 的余数分别是 $\textit{curr}$ 和 $\textit{prev}$ 的最长有效子序列，然后在末尾添加 $\textit{num}$ 得到更长的有效子序列，因此将 $\textit{dp}[\textit{prev}][\textit{curr}]$ 的值更新为 $\textit{dp}[\textit{curr}][\textit{prev}] + 1$，然后使用 $\textit{dp}[\textit{prev}][\textit{curr}]$ 更新最长有效子序列的长度。
上述计算过程即为动态规划的状态转移方程。
遍历结束之后，即可得到最长有效子序列的长度。
代码
###Java
class Solution {
public int maximumLength(int[] nums) {
return maximumLength(nums, 2);
}
public int maximumLength(int[] nums, int k) {
int maxLength = 0;
int[][] dp = new int[k][k];
for (int num : nums) {
int curr = num % k;
for (int prev = 0; prev < k; prev++) {
dp[prev][curr] = dp[curr][prev] + 1;
maxLength = Math.max(maxLength, dp[prev][curr]);
}
}
return maxLength;
}
}
###C#
public class Solution {
public int MaximumLength(int[] nums) {
return MaximumLength(nums, 2);
}
public int MaximumLength(int[] nums, int k) {
int maxLength = 0;
int[][] dp = new int[k][];
for (int i = 0; i < k; i++) {
dp[i] = new int[k];
}
foreach (int num in nums) {
int curr = num % k;
for (int prev = 0; prev < k; prev++) {
dp[prev][curr] = dp[curr][prev] + 1;
maxLength = Math.Max(maxLength, dp[prev][curr]);
}
}
return maxLength;
}
}
复杂度分析
-
时间复杂度：$O(k^2 + nk)$，其中 $k$ 是给定的整数，这道题中 $k = 2$，$n$ 是数组 $\textit{nums}$ 的长度。创建大小为 $k \times k$ 的二维数组 $\textit{dp}$ 的时间是 $O(k^2)$，遍历数组 $\textit{nums}$ 时对于每个元素的计算时间是 $O(k)$，因此时间复杂度是 $O(k^2 + nk)$。
-
空间复杂度：$O(k^2)$，其中 $k$ 是给定的整数，这道题中 $k = 2$。需要创建大小为 $k \times k$ 的二维数组。
登录
