3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution

In this guide, you will get 3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Length of a Good Subsequence I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find the Maximum Length of a Good Subsequence I solution in C++
4. Find the Maximum Length of a Good Subsequence I solution in Java
5. Find the Maximum Length of a Good Subsequence I solution in Python
6. Additional Resources

Problem Statement of Find the Maximum Length of a Good Subsequence I

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 <= 500
1 <= nums[i] <= 109
0 <= k <= min(nums.length, 25)

Complexity Analysis

• Time Complexity: O(nk)
• Space Complexity: O(nk)

3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution in C++

class Solution {
 public:
  int maximumLength(vector<int>& nums, int k) {
    // dp[count][num] := the maximum length of a good subsequence with at most
    // `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    vector<unordered_map<int, int>> dp(k + 1);
    // maxLen[count] := the maximum length of a good subsequence with `count`
    // indices where seq[i] != seq[i + 1]
    vector<int> maxLen(k + 1);

    for (const int num : nums)
      for (int count = k; count >= 0; --count) {
        // Append `num` to the subsequence.
        ++dp[count][num];
        if (count > 0)
          dp[count][num] = max(dp[count][num], maxLen[count - 1] + 1);
        maxLen[count] = max(maxLen[count], dp[count][num]);
      }

    return maxLen[k];
  }
};
/* code provided by PROGIEZ */

3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution in Java

class Solution {
  public int maximumLength(int[] nums, int k) {
    // dp[count][num] := the maximum length of a good subsequence with at most
    // `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    Map<Integer, Integer>[] dp = new HashMap[k + 1];
    // maxLen[count] := the maximum length of a good subsequence with `count`
    // indices where seq[i] != seq[i + 1]
    int[] maxLen = new int[k + 1];

    for (int i = 0; i <= k; ++i)
      dp[i] = new HashMap<>();

    for (final int num : nums)
      for (int count = k; count >= 0; --count) {
        // Append `num` to the subsequence.
        dp[count].merge(num, 1, Integer::sum);
        if (count > 0)
          dp[count].merge(num, maxLen[count - 1] + 1, Math::max);
        maxLen[count] = Math.max(maxLen[count], dp[count].get(num));
      }

    return maxLen[k];
  }
}
// code provided by PROGIEZ

3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution in Python

class Solution:
  def maximumLength(self, nums: list[int], k: int) -> int:
    # dp[count][num] := the maximum length of a good subsequence with at most
    # `count` indices where seq[i] != seq[i + 1] and it ends in `num`.
    dp = [collections.Counter() for _ in range(k + 1)]
    # maxLen[count] := the maximum length of a good subsequence with `count`
    # indices where seq[i] != seq[i + 1]
    maxLen = [0] * (k + 1)

    for num in nums:
      for count in range(k, -1, -1):
        # Append `num` to the subsequence.
        dp[count][num] += 1
        if count > 0:
          dp[count][num] = max(dp[count][num], maxLen[count - 1] + 1)
        maxLen[count] = max(maxLen[count], dp[count][num])

    return maxLen[k]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.