Description
You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].
Return the maximum possible length of a good subsequence of nums.
Example 1:
Input: nums = [1,2,1,1,3], k = 2
Output: 4
Explanation:
The maximum length subsequence is [1,2,1,1,3].
Example 2:
Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation:
The maximum length subsequence is [1,2,3,4,5,1].
Constraints:
1 <= nums.length <= 5 * 1031 <= nums[i] <= 1090 <= k <= min(50, nums.length)
Solution
Python3
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
N = len(nums)
# dp[i][j] -> the length of the longest subseq from index i till N with j indices
dp = [[0] * (k + 1) for _ in range(N)]
max_dp = [0] * (k + 1)
prev = {}
res = 0
for i in range(N - 1, -1, -1):
p = prev[nums[i]] if nums[i] in prev else i
for j in range(k, -1, -1):
dp[i][j] = max(1 + (dp[p][j] if i != p else 0), 1 + (max_dp[j - 1] if j > 0 else 0))
max_dp[j] = max(max_dp[j], dp[i][j])
prev[nums[i]] = i
res = max(res, dp[i][k])
return res