class Solution {
public:
int maximumLength(vector<int>& nums) {
}
};
100357. 找出有效子序列的最大长度 I
给你一个整数数组 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 * 1051 <= nums[i] <= 107原站题解
golang 解法, 执行用时: 91 ms, 内存消耗: 12.3 MB, 提交时间: 2024-07-02 22:15:46
func maximumLength(nums []int) (ans int) {
k := 2
f := make([][]int, k)
for i := range f {
f[i] = make([]int, k)
}
for _, x := range nums {
x %= k
for y, fxy := range f[x] {
f[y][x] = fxy + 1
ans = max(ans, f[y][x])
}
}
return
}
func maximumLength2(nums []int) (ans int) {
k := 2
f := make([]int, k)
for m := 0; m < k; m++ {
clear(f)
for _, x := range nums {
x %= k
f[x] = f[(m-x+k)%k] + 1
ans = max(ans, f[x])
}
}
return
}
cpp 解法, 执行用时: 125 ms, 内存消耗: 92.4 MB, 提交时间: 2024-07-02 22:14:53
class Solution {
public:
int maximumLength(vector<int>& nums) {
int k = 2;
int ans = 0;
for (int m = 0; m < k; m++) {
vector<int> f(k);
for (int x : nums) {
x %= k;
f[x] = f[(m - x + k) % k] + 1;
ans = max(ans, f[x]);
}
}
return ans;
}
int maximumLength2(vector<int>& nums) {
int k = 2;
int ans = 0;
vector<vector<int>> f(k, vector<int>(k));
for (int x : nums) {
x %= k;
for (int y = 0; y < k; y++) {
f[y][x] = f[x][y] + 1;
ans = max(ans, f[y][x]);
}
}
return ans;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 62.9 MB, 提交时间: 2024-07-02 22:13:59
class Solution {
public int maximumLength(int[] nums) {
int k = 2;
int ans = 0;
int[][] f = new int[k][k];
for (int x : nums) {
x %= k;
for (int y = 0; y < k; y++) {
f[y][x] = f[x][y] + 1;
ans = Math.max(ans, f[y][x]);
}
}
return ans;
}
public int maximumLength2(int[] nums) {
int k = 2;
int ans = 0;
for (int m = 0; m < k; m++) {
int[] f = new int[k];
for (int x : nums) {
x %= k;
f[x] = f[(m - x + k) % k] + 1;
ans = Math.max(ans, f[x]);
}
}
return ans;
}
}
python3 解法, 执行用时: 171 ms, 内存消耗: 37.5 MB, 提交时间: 2024-07-02 22:12:55
class Solution:
def maximumLength(self, nums: List[int]) -> int:
k = 2
f = [[0] * k for _ in range(k)]
for x in nums:
x %= k
for y, fxy in enumerate(f[x]):
f[y][x] = fxy + 1
return max(map(max, f))
def maximumLength2(self, nums: List[int]) -> int:
k = 2
ans = 0
for m in range(k):
f = [0] * k
for x in nums:
x %= k
f[x] = f[m - x] + 1
ans = max(ans, max(f))
return ans
def maximumLength3(self, nums: List[int]) -> int:
k = 2
f = [0] * (k * k)
for x in nums:
x %= k
# f[x * k: (x + 1) * k] 是二维写法的第 x 行
# f[x::k] 是二维写法的第 x 列
f[x::k] = [v + 1 for v in f[x * k: (x + 1) * k]]
return max(f)