Welcome to Subscribe On Youtube
3176. Find the Maximum Length of a Good Subsequence I
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 <= 5001 <= nums[i] <= 1090 <= k <= min(nums.length, 25)
Solutions
Solution 1: Dynamic Programming
We define $f[i][h]$ as the length of the longest good subsequence ending with $nums[i]$ and having no more than $h$ indices satisfying the condition. Initially, $f[i][h] = 1$. The answer is $\max(f[i][k])$, where $0 \le i < n$.
We consider how to calculate $f[i][h]$. We can enumerate $0 \le j < i$, if $nums[i] = nums[j]$, then $f[i][h] = \max(f[i][h], f[j][h] + 1)$; otherwise, if $h > 0$, then $f[i][h] = \max(f[i][h], f[j][h - 1] + 1)$. That is:
\[f[i][h]= \begin{cases} \max(f[i][h], f[j][h] + 1), & \text{if } nums[i] = nums[j], \\ \max(f[i][h], f[j][h - 1] + 1), & \text{if } h > 0. \end{cases}\]The final answer is $\max(f[i][k])$, where $0 \le i < n$.
The time complexity is $O(n^2 \times k)$, and the space complexity is $O(n \times k)$. Where $n$ is the length of the array nums.
-
class Solution { public int maximumLength(int[] nums, int k) { int n = nums.length; int[][] f = new int[n][k + 1]; int ans = 0; for (int i = 0; i < n; ++i) { for (int h = 0; h <= k; ++h) { for (int j = 0; j < i; ++j) { if (nums[i] == nums[j]) { f[i][h] = Math.max(f[i][h], f[j][h]); } else if (h > 0) { f[i][h] = Math.max(f[i][h], f[j][h - 1]); } } ++f[i][h]; } ans = Math.max(ans, f[i][k]); } return ans; } } -
class Solution { public: int maximumLength(vector<int>& nums, int k) { int n = nums.size(); int f[n][k + 1]; memset(f, 0, sizeof(f)); int ans = 0; for (int i = 0; i < n; ++i) { for (int h = 0; h <= k; ++h) { for (int j = 0; j < i; ++j) { if (nums[i] == nums[j]) { f[i][h] = max(f[i][h], f[j][h]); } else if (h) { f[i][h] = max(f[i][h], f[j][h - 1]); } } ++f[i][h]; } ans = max(ans, f[i][k]); } return ans; } }; -
class Solution: def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) f = [[1] * (k + 1) for _ in range(n)] ans = 0 for i, x in enumerate(nums): for h in range(k + 1): for j, y in enumerate(nums[:i]): if x == y: f[i][h] = max(f[i][h], f[j][h] + 1) elif h: f[i][h] = max(f[i][h], f[j][h - 1] + 1) ans = max(ans, f[i][k]) return ans -
func maximumLength(nums []int, k int) (ans int) { f := make([][]int, len(nums)) for i := range f { f[i] = make([]int, k+1) } for i, x := range nums { for h := 0; h <= k; h++ { for j, y := range nums[:i] { if x == y { f[i][h] = max(f[i][h], f[j][h]) } else if h > 0 { f[i][h] = max(f[i][h], f[j][h-1]) } } f[i][h]++ } ans = max(ans, f[i][k]) } return } -
function maximumLength(nums: number[], k: number): number { const n = nums.length; const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0)); let ans = 0; for (let i = 0; i < n; ++i) { for (let h = 0; h <= k; ++h) { for (let j = 0; j < i; ++j) { if (nums[i] === nums[j]) { f[i][h] = Math.max(f[i][h], f[j][h]); } else if (h) { f[i][h] = Math.max(f[i][h], f[j][h - 1]); } } ++f[i][h]; } ans = Math.max(ans, f[i][k]); } return ans; }