LeetCode-in-Java

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 java.util.HashMap;

public class Solution {
    public int maximumLength(int[] nums, int k) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        int n = nums.length;
        int[] pre = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = hm.getOrDefault(nums[i], -1);
            hm.put(nums[i], i);
        }
        int[][] dp = new int[k + 1][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
            if (pre[i] >= 0) {
                dp[0][i] = dp[0][pre[i]] + 1;
            }
        }
        for (int i = 1; i <= k; i++) {
            int max = 0;
            for (int j = 0; j < n; j++) {
                if (pre[j] >= 0) {
                    dp[i][j] = dp[i][pre[j]] + 1;
                }
                dp[i][j] = Math.max(dp[i][j], max + 1);
                max = Math.max(max, dp[i - 1][j]);
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[k][i]);
        }
        return max;
    }
}

This site is open source. Improve this page.