[LeetCode 3202] Find the Maximum Length of Valid Subsequence II

문제 바로가기

Description

---

You are given an integer array nums and a positive integer k. A subsequence sub of nums with length x is called valid if it satisfies:

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

Return the length of the longest valid subsequence of nums.

Example 1

---

• Input: nums = [1,2,3,4,5], k = 2
• Output: 5
• Explanation:
  • The longest valid subsequence is [1, 2, 3, 4, 5].

Example 2

---

• Input: nums = [1,4,2,3,1,4], k = 3
• Output: 4
• Explanation:
  • The longest valid subsequence is [1, 4, 1, 4].

Constraints

---

• 2 <= nums.length <= 10^3
• 1 <= nums[i] <= 10^7
• 1 <= k <= 10^3

Hint

---

Hint 1

  Fix the value of `(subs[0] + subs[1]) % k` from the `k` possible values. Let it be `val`.
	

Hint 2

  Let `dp[i]` store the maximum length of a subsequence with its last element `x` such that `x % k == i`.
	

Hint 3

  Answer for a subsequence ending at index `y` is `dp[(k + val - (y % k)) % k] + 1`.
	

Code

---

내 제출

---

class Solution {
    public int maximumLength(int[] nums, int k) {
        int[][] f = new int[k][k];
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = Math.max(ans, f[x][y]);
            }
        }
        return ans;
    }
}

Runtime	Memory
40 ms	53.9 MB

다른 풀이

---

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int[][] maxLen = new int[k + 1][n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int mod = (nums[i] + nums[j]) % k;
                if (i == 0) {
                    maxLen[mod][j] = 2;
                } else {
                    maxLen[mod][j] = Math.max(maxLen[mod][i] + 1, 2);
                }
                max = Math.max(max, maxLen[mod][j]);
            }
        }
        return max;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/3200-3299/3202.Find%20the%20Maximum%20Length%20of%20Valid%20Subsequence%20II/Solution.java