class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
}
};
100358. 找出有效子序列的最大长度 II
给你一个整数数组nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % knums 的 最长有效子序列 的长度。
示例 1：
输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：
最长有效子序列是 [1, 2, 3, 4, 5] 。
示例 2：
输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：
最长有效子序列是 [1, 4, 1, 4] 。
提示：
2 <= nums.length <= 1031 <= nums[i] <= 1071 <= k <= 103原站题解
golang 解法, 执行用时: 67 ms, 内存消耗: 18.3 MB, 提交时间: 2024-07-02 22:15:21
func maximumLength(nums []int, k int) (ans int) {
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, k int) (ans int) {
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 解法, 执行用时: 112 ms, 内存消耗: 124 MB, 提交时间: 2024-07-02 22:14:28
class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
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) {
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 解法, 执行用时: 31 ms, 内存消耗: 53 MB, 提交时间: 2024-07-02 22:13:34
class Solution {
public int maximumLength(int[] nums, int k) {
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) {
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 解法, 执行用时: 817 ms, 内存消耗: 24.1 MB, 提交时间: 2024-07-02 22:10:57
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
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], k: int) -> int:
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], k: int) -> int:
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)