Welcome to Subscribe On Youtube
3177. Find the Maximum Length of a Good Subsequence II
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 <= 5 * 1031 <= nums[i] <= 1090 <= k <= min(50, nums.length)
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.
Due to the large data range of this problem, the above solution will time out and needs to be optimized.
According to the state transition equation, if $nums[i] = nums[j]$, then we only need to get the maximum value of $f[j][h]$, we can maintain it with an array $mp$ of length $k + 1$. If $nums[i] \neq nums[j]$, we need to record the maximum value of $f[j][h - 1]$ corresponding to $nums[j]$, the maximum value and the second maximum value, we can maintain it with an array $g$ of length $k + 1$.
The time complexity is $O(n \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]; Map<Integer, Integer>[] mp = new HashMap[k + 1]; Arrays.setAll(mp, i -> new HashMap<>()); int[][] g = new int[k + 1][3]; int ans = 0; for (int i = 0; i < n; ++i) { for (int h = 0; h <= k; ++h) { f[i][h] = mp[h].getOrDefault(nums[i], 0); if (h > 0) { if (g[h - 1][0] != nums[i]) { f[i][h] = Math.max(f[i][h], g[h - 1][1]); } else { f[i][h] = Math.max(f[i][h], g[h - 1][2]); } } ++f[i][h]; mp[h].merge(nums[i], f[i][h], Integer::max); if (g[h][0] != nums[i]) { if (f[i][h] >= g[h][1]) { g[h][2] = g[h][1]; g[h][1] = f[i][h]; g[h][0] = nums[i]; } else { g[h][2] = Math.max(g[h][2], f[i][h]); } } else { g[h][1] = Math.max(g[h][1], f[i][h]); } ans = Math.max(ans, f[i][h]); } } return ans; } } -
class Solution { public: int maximumLength(vector<int>& nums, int k) { int n = nums.size(); vector<vector<int>> f(n, vector<int>(k + 1)); vector<unordered_map<int, int>> mp(k + 1); vector<vector<int>> g(k + 1, vector<int>(3)); int ans = 0; for (int i = 0; i < n; ++i) { for (int h = 0; h <= k; ++h) { f[i][h] = mp[h][nums[i]]; if (h > 0) { if (g[h - 1][0] != nums[i]) { f[i][h] = max(f[i][h], g[h - 1][1]); } else { f[i][h] = max(f[i][h], g[h - 1][2]); } } ++f[i][h]; mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]); if (g[h][0] != nums[i]) { if (f[i][h] >= g[h][1]) { g[h][2] = g[h][1]; g[h][1] = f[i][h]; g[h][0] = nums[i]; } else { g[h][2] = max(g[h][2], f[i][h]); } } else { g[h][1] = max(g[h][1], f[i][h]); } ans = max(ans, f[i][h]); } } return ans; } }; -
class Solution: def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) f = [[0] * (k + 1) for _ in range(n)] mp = [defaultdict(int) for _ in range(k + 1)] g = [[0] * 3 for _ in range(k + 1)] ans = 0 for i, x in enumerate(nums): for h in range(k + 1): f[i][h] = mp[h][x] if h: if g[h - 1][0] != nums[i]: f[i][h] = max(f[i][h], g[h - 1][1]) else: f[i][h] = max(f[i][h], g[h - 1][2]) f[i][h] += 1 mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]) if g[h][0] != x: if f[i][h] >= g[h][1]: g[h][2] = g[h][1] g[h][1] = f[i][h] g[h][0] = x else: g[h][2] = max(g[h][2], f[i][h]) else: g[h][1] = max(g[h][1], f[i][h]) ans = max(ans, f[i][h]) return ans -
func maximumLength(nums []int, k int) int { n := len(nums) f := make([][]int, n) for i := range f { f[i] = make([]int, k+1) } mp := make([]map[int]int, k+1) for i := range mp { mp[i] = make(map[int]int) } g := make([][3]int, k+1) ans := 0 for i := 0; i < n; i++ { for h := 0; h <= k; h++ { f[i][h] = mp[h][nums[i]] if h > 0 { if g[h-1][0] != nums[i] { if g[h-1][1] > f[i][h] { f[i][h] = g[h-1][1] } } else { if g[h-1][2] > f[i][h] { f[i][h] = g[h-1][2] } } } f[i][h]++ if f[i][h] > mp[h][nums[i]] { mp[h][nums[i]] = f[i][h] } if g[h][0] != nums[i] { if f[i][h] >= g[h][1] { g[h][2] = g[h][1] g[h][1] = f[i][h] g[h][0] = nums[i] } else if f[i][h] > g[h][2] { g[h][2] = f[i][h] } } else { if f[i][h] > g[h][1] { g[h][1] = f[i][h] } } if f[i][h] > ans { ans = f[i][h] } } } return ans } -
function maximumLength(nums: number[], k: number): number { const n = nums.length; const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0)); const mp: Map<number, number>[] = Array.from({ length: k + 1 }, () => new Map()); const g: number[][] = Array.from({ length: k + 1 }, () => Array(3).fill(0)); let ans = 0; for (let i = 0; i < n; i++) { for (let h = 0; h <= k; h++) { f[i][h] = mp[h].get(nums[i]) || 0; if (h > 0) { if (g[h - 1][0] !== nums[i]) { f[i][h] = Math.max(f[i][h], g[h - 1][1]); } else { f[i][h] = Math.max(f[i][h], g[h - 1][2]); } } f[i][h]++; mp[h].set(nums[i], Math.max(mp[h].get(nums[i]) || 0, f[i][h])); if (g[h][0] !== nums[i]) { if (f[i][h] >= g[h][1]) { g[h][2] = g[h][1]; g[h][1] = f[i][h]; g[h][0] = nums[i]; } else { g[h][2] = Math.max(g[h][2], f[i][h]); } } else { g[h][1] = Math.max(g[h][1], f[i][h]); } ans = Math.max(ans, f[i][h]); } } return ans; }