LeetCode in Kotlin

3177. Find the Maximum Length of a Good Subsequence II

Hard

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 * 103
• 1 <= nums[i] <= 109
• 0 <= k <= min(50, nums.length)

Solution

import kotlin.math.max

class Solution {
    fun maximumLength(nums: IntArray, k: Int): Int {
        val hm = HashMap<Int, Int>()
        val n = nums.size
        val pre = IntArray(n)
        for (i in 0 until n) {
            pre[i] = hm.getOrDefault(nums[i], -1)
            hm[nums[i]] = i
        }
        val dp = Array(k + 1) { IntArray(n) }
        for (i in 0 until n) {
            dp[0][i] = 1
            if (pre[i] >= 0) {
                dp[0][i] = dp[0][pre[i]] + 1
            }
        }
        for (i in 1..k) {
            var max = 0
            for (j in 0 until n) {
                if (pre[j] >= 0) {
                    dp[i][j] = dp[i][pre[j]] + 1
                }
                dp[i][j] = max(dp[i][j], (max + 1))
                max = max(max, dp[i - 1][j])
            }
        }
        var max = 0
        for (i in 0 until n) {
            max = max(max, dp[k][i])
        }
        return max
    }
}

This site is open source. Improve this page.