当前位置：首页 > article >正文

【从零开始的LeetCode-算法】3202. 找出有效子序列的最大长度 II

article 2024/11/29 3:57:28

给你一个整数数组 nums 和一个正整数 k 。

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

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

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

示例 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 <= 10^3
1 <= nums[i] <= 10^7
1 <= k <= 10^3

我的解答：

class Solution {
    public int maximumLength(int[] nums, int k) {
        int[][] k_num = new int[k][k];
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            int x = nums[i] % k;
            for(int y =0; y < k; y++){
                k_num[y][x] = k_num[x][y] + 1;
                res = Math.max(res,k_num[y][x]);
            }
        }
        return res;
    }
}