找出有效子序列的最大长度 II

Posted on Jul 04, 2024 By ᵇᵒ

Find the Maximum Length of Valid Subsequence II

LeetCode 3202

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\)

2D dp solution

dp[i][j] 表示以 ...,i,j 结尾的子串长度, 其子串形式为 ...i,j,i,j（假设数组每个元素已对 k 求模，子串形式必为 i、j 交替）， 其长度为 ...,j,i 子串长度加 1，也即 dp[i][j] = dp[j][i] + 1

class Solution {
    fun maximumLength(nums: IntArray, k: Int): Int {
        val dp = Array(k) { IntArray(k) }
        var ans = 0
        nums.forEach { i ->
            repeat(k) { j ->
                dp[j][i.mod(k)] = dp[i.mod(k)][j] + 1
                ans = ans.coerceAtLeast(dp[j][i.mod(k)])
            }
        }
        return ans
    }
}

1D dp solution

令 i = (sub[0] + sub[1]) % k，则 dp[j % k] 表示 以 j % k 结尾的最长子串长度

class Solution {
    fun maximumLength(nums: IntArray, k: Int): Int {
        var ans = 0
        repeat(k) { i ->
            val dp = IntArray(k)
            nums.forEach { j ->
                dp[j.mod(k)] = dp[(i - j.mod(k) + k).mod(k)] + 1
                ans = ans.coerceAtLeast(dp[j.mod(k)])
            }
        }
        return ans
    }
}