Skip to content

3177. Find the Maximum Length of a Good Subsequence II 👍

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  // Same as 3176. Find the Maximum Length of a Good Subsequence I
  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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  // Same as 3176. Find the Maximum Length of a Good Subsequence I
  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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  # Same as 3176. Find the Maximum Length of a Good Subsequence I
  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]