3177. Find the Maximum Length of a Good Subsequence II

Intuition

To find the longest good subsequence where there are at most k changes allowed (i.e., adjacent elements that are different), we can use dynamic programming. The idea is to maintain a DP table that tracks the length of the longest good subsequence ending at each index with a certain number of changes. By iterating through the array and updating this table based on the conditions specified, we can find the maximum length of such a subsequence.

Approach

1. Define the DP Array: - Use a 2D DP array dp[i][j], where i is the index in nums and j represents the number of changes allowed (from 0 to k). - dp[i][j] stores the length of the longest good subsequence that ends at index i with exactly j changes.
2. Initialize the DP Array: - Set dp[i][0] to 1 for all i because a single element subsequence is always a good subsequence with 0 changes.
3. Fill the DP Array: - For each element nums[i], check all previous elements nums[p] (where p < i). - If nums[p] == nums[i], extend the subsequence without adding a change. - If nums[p] != nums[i] and j > 0, extend the subsequence with one additional change.
4. Keep Track of the Maximum Length: - Continuously update the maximum length of the good subsequence found.

Approach Transition: From O(n^2*k) to O(n*k)

Problem Understanding

Given an integer array nums and a non-negative integer k, find the maximum possible length of a good subsequence, where a good subsequence allows at most k adjacent indices with unequal elements.

Initial Solution: O(n^2*k)

Dynamic Programming Approach

Step 1: Initialize DP Table

• Create a 2D DP array dp of size n x (k+1) and initialize all values to 0.
• Each dp[i][j] represents the length of the longest good subsequence ending at index i with j changes.

Step 2: Base Case

• For each index i, if no changes are allowed (j == 0), set dp[i][0] = 1.
• This initializes the longest subsequence length as 1 for each element in the array.

Step 3: Fill the DP Table

• For each index i from 1 to n-1: - For each value of j from 0 to k: - Initialize dp[i][j] = 1. - Iterate through all indices p from 0 to i-1: - If nums[p] equals nums[i], update dp[i][j] to max(dp[i][j], dp[p][j] + 1). - If j > 0, update dp[i][j] to max(dp[i][j], dp[p][j - 1] + 1) to allow for a change.

Complexity Analysis:

• Time Complexity: O(n^2*k)
• Space Complexity: O(n*k) for the DP table.

Optimized Solution: O(n*k)

Rolling Sum Optimization

Idea

• Utilize a rolling sum approach to optimize the inner loop, reducing the time complexity to O(n*k).

Step 1: Initialize DP Table and Variables

• Create a 2D DP array dp of size n x (k+1) and initialize all values to 0.
• Initialize res to 1.

Step 2: Base Case

• For each index i, if no changes are allowed (j == 0), set dp[i][0] = 1.

Step 3: Fill the DP Table

• For each value of j from 0 to k: - Initialize max1 = 1 to track the maximum length of subsequence with j-1 changes up to the previous index. - Initialize a map to track the last occurrence index of each number. - Iterate through each index i from 1 to n-1: - Update dp[i][j] based on the previous values and conditions as described in the initial solution. - Update res to the maximum length encountered. - Utilize the map to efficiently find the last occurrence index of each number.

Complexity

• Time complexity: O(n \* k) - We iterate through the array nums with two nested loops: one for k and one for the length n of the array. In each iteration, operations such as dictionary lookups and updates are done in constant time.
• Space complexity: O(n \* k) - The DP table requires O(n \* k) space to store the results for each index and number of changes. Additionally, the space for the dictionary is proportional to the number of unique elements in nums, which in the worst case is O(n).

Code

C++

class Solution {
public:
    int maximumLength(std::vector& nums, int k) {
        int n = nums.size();
        if (n == 0) return 0;

        std::vector> dp(n, std::vector(k + 1, 0));
        for (int i = 0; i < n; ++i) dp[i][0] = 1;

        int res = 1;
        for (int j = 0; j <= k; ++j) {
            int max1 = 1;
            std::unordered_map numMap;
            numMap[nums[0]] = 0;

            for (int i = 1; i < n; ++i) {
                dp[i][j] = 1;
                if (i > 0 && j > 0) max1 = std::max(max1, dp[i - 1][j - 1] + 1);
                dp[i][j] = std::max(dp[i][j], max1);

                if (numMap.find(nums[i]) != numMap.end()) {
                    dp[i][j] = std::max(dp[i][j], dp[numMap[nums[i]]][j] + 1);
                }

                numMap[nums[i]] = i;
                res = std::max(res, dp[i][j]);
            }
        }

        return res;
    }
};

Python

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return 0

        dp = [[0] * (k + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = 1

        res = 1
        for j in range(k + 1):
            max1 = 1
            num_map = {nums[0]: 0}

            for i in range(1, n):
                dp[i][j] = 1
                if i > 0 and j > 0:
                    max1 = max(max1, dp[i - 1][j - 1] + 1)
                dp[i][j] = max(dp[i][j], max1)

                if nums[i] in num_map:
                    dp[i][j] = max(dp[i][j], dp[num_map[nums[i]]][j] + 1)

                num_map[nums[i]] = i
                res = max(res, dp[i][j])

        return res

Java

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return 0;

        int[][] dp = new int[n][k + 1];
        for (int i = 0; i < n; ++i) dp[i][0] = 1;

        int res = 1;
        for (int j = 0; j <= k; ++j) {
            int max1 = 1;
            Map numMap = new HashMap<>();
            numMap.put(nums[0], 0);

            for (int i = 1; i < n; ++i) {
                dp[i][j] = 1;
                if (i > 0 && j > 0) max1 = Math.max(max1, dp[i - 1][j - 1] + 1);
                dp[i][j] = Math.max(dp[i][j], max1);

                if (numMap.containsKey(nums[i])) {
                    dp[i][j] = Math.max(dp[i][j], dp[numMap.get(nums[i])][j] + 1);
                }

                numMap.put(nums[i], i);
                res = Math.max(res, dp[i][j]);
            }
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumLength = function (nums, k) {
    const n = nums.length;
    if (n === 0) return 0;
    const dp = Array.from({ length: n }, () => Array(k + 1).fill(0));
    for (let i = 0; i < n; ++i) dp[i][0] = 1;

    let res = 1;
    for (let j = 0; j <= k; ++j) {
        var max1 = 1;
        var map = new Map();
        map.set(nums[0], 0);
        for (let i = 1; i < n; ++i) {
            dp[i][j] = 1;
            if (i > 0 && j > 0) max1 = Math.max(max1, dp[i - 1][j - 1] + 1);
            dp[i][j] = Math.max(dp[i][j], max1);
            if (map.has(nums[i])) {
                dp[i][j] = Math.max(dp[i][j], dp[map.get(nums[i])][j] + 1);
            }
            map.set(nums[i], i);
            res = Math.max(res, dp[i][j]);
        }
    }

    return res;
};

Go

func maximumLength(nums []int, k int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    for i := 0; i < n; i++ {
        dp[i][0] = 1
    }

    res := 1
    for j := 0; j <= k; j++ {
        max1 := 1
        numMap := make(map[int]int)
        numMap[nums[0]] = 0
        for i := 1; i < n; i++ {
            dp[i][j] = 1
            if i > 0 && j > 0 {
                max1 = max(max1, dp[i-1][j-1]+1)
            }
            dp[i][j] = max(dp[i][j], max1)
            if idx, exists := numMap[nums[i]]; exists {
                dp[i][j] = max(dp[i][j], dp[idx][j]+1)
            }
            numMap[nums[i]] = i
            res = max(res, dp[i][j])
        }
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

C#

public class Solution {
    public int MaximumLength(int[] nums, int k) {
        int n = nums.Length;
        if (n == 0) return 0;

        int[][] dp = new int[n][];
        for (int i = 0; i < n; ++i) {
            dp[i] = new int[k + 1];
        }
        for (int i = 0; i < n; ++i) dp[i][0] = 1;

        int res = 1;
        for (int j = 0; j <= k; ++j) {
            int max1 = 1;
            Dictionary numMap = new Dictionary();
            numMap[nums[0]] = 0;

            for (int i = 1; i < n; ++i) {
                dp[i][j] = 1;
                if (i > 0 && j > 0) max1 = Math.Max(max1, dp[i - 1][j - 1] + 1);
                dp[i][j] = Math.Max(dp[i][j], max1);

                if (numMap.ContainsKey(nums[i])) {
                    dp[i][j] = Math.Max(dp[i][j], dp[numMap[nums[i]]][j] + 1);
                }

                numMap[nums[i]] = i;
                res = Math.Max(res, dp[i][j]);
            }
        }

        return res;
    }
}

Conclusion

By utilizing dynamic programming, we effectively track the longest good subsequence ending at each index with a certain number of allowed changes. This method ensures that we consider all possible subsequences and changes efficiently. The algorithm operates within acceptable time and space complexities, making it suitable for large input sizes typical in competitive programming and coding interviews.