LeetCode in Kotlin
3176. Find the Maximum Length of a Good Subsequence I
Medium
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 <= 5001 <= nums[i] <= 1090 <= k <= min(nums.length, 25)
Solution
import kotlin.math.max
class Solution {
fun maximumLength(nums: IntArray, k: Int): Int {
val n = nums.size
var count = 0
for (i in 0 until nums.size - 1) {
if (nums[i] != nums[i + 1]) {
count++
}
}
if (count <= k) {
return n
}
val max = IntArray(k + 1)
max.fill(1)
val vis = IntArray(n)
vis.fill(-1)
val map = HashMap<Int, Int>()
for (i in 0 until n) {
if (!map.containsKey(nums[i])) {
map[nums[i]] = i + 1
} else {
vis[i] = map[nums[i]]!! - 1
map[nums[i]] = i + 1
}
}
val dp = Array(n) { IntArray(k + 1) }
for (i in 0 until n) {
for (j in 0..k) {
dp[i][j] = 1
}
}
for (i in 1 until n) {
for (j in k - 1 downTo 0) {
dp[i][j + 1] = max(dp[i][j + 1], (1 + max[j]))
max[j + 1] = max(max[j + 1], dp[i][j + 1])
}
if (vis[i] != -1) {
val a = vis[i]
for (j in 0..k) {
dp[i][j] = max(dp[i][j], (1 + dp[a][j]))
max[j] = max(dp[i][j], max[j])
}
}
}
var ans = 1
for (i in 0..k) {
ans = max(ans, max[i])
}
return ans
}
}