3176. Find the Maximum Length of a Good Subsequence I

Problem Link

Description

---

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)

Solution

---

Python3

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        N = len(nums)
        # dp[i][j] -> the length of the longest subseq from index i till N with j indices
        dp = [[0] * (k + 1) for _ in range(N)]
        max_dp = [0] * (k + 1)
        prev = {}
        res = 0
 
        for i in range(N - 1, -1, -1):
            p = prev[nums[i]] if nums[i] in prev else i
 
            for j in range(k, -1, -1):
                dp[i][j] = max(1 + (dp[p][j] if i != p else 0), 1 + (max_dp[j - 1] if j > 0 else 0))
                max_dp[j] = max(max_dp[j], dp[i][j])
            
            prev[nums[i]] = i
            res = max(res, dp[i][k])
        
        return res

C++

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
class Solution {
public:
    int N;
    int cache[505][505][26];
 
    int dp(int index, int prev, int count, vector<int>& nums, int k) {
        if (index == N) return 0;
 
        // Check the cache
        if (cache[index][prev + 1][count] != -1) {
            return cache[index][prev + 1][count];
        }
 
        int res = INT_MIN;
 
        // Case 1: skip the current element
        res = dp(index + 1, prev, count, nums, k);
 
        // Case 2: take the current element
        if (prev != -1) {
            if (nums[index] != nums[prev]) {
                if (count + 1 <= k) {
                    res = max(res, 1 + dp(index + 1, index, count + 1, nums, k));
                }
            } else {
                res = max(res, 1 + dp(index + 1, index, count, nums, k));
            }
        } else {
            res = max(res, 1 + dp(index + 1, index, count, nums, k));
        }
 
        // Store the result in the cache and return
        cache[index][prev + 1][count] = res;
        return res;
    }
 
    int maximumLength(vector<int>& nums, int k) {
        N = nums.size();
        memset(cache, -1, sizeof(cache));
        return dp(0, -1, 0, nums, k);
    }
};