Skip to content

3177. Find the Maximum Length of a Good Subsequence II

SourceBiweekly Contest 132 Q4DifficultyHardRating2364

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 * 103
  • 1 <= nums[i] <= 109
  • 0 <= k <= min(50, nums.length)

Solutions

Solution 1: Dynamic Programming

Thinking

The definition matches part I, but \(n\) rules out \(O(n^2k)\). The recurrence itself is unchanged.

Equal values take the historical best of that value; a change takes the best at \(h-1\), or the second best when that best is the current value.

Read \(f[i][h]\) from \(mp\) and \(g\), then write the new extrema back. The answer is the global maximum \(f[i][h]\).

We define \(f[i][h]\) as the length of the longest good subsequence ending with \(\textit{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 \(\textit{nums}[i] = \textit{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 } \textit{nums}[i] = \textit{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^2k)\), and the space complexity is \(O(nk)\), where \(n\) is the length of the array \(\textit{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 \(\textit{nums}[i] = \textit{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 \(\textit{nums}[i] \neq \textit{nums}[j]\), we need to record the maximum value of \(f[j][h - 1]\) corresponding to \(\textit{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(nk)\), and the space complexity is \(O(nk)\), where \(n\) is the length of the array \(\textit{nums}\).

 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
26
27
28
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

 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
26
27
28
29
30
31
32
33
34
35
36
37
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;
    }
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
    }
};

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
}

 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
26
27
28
29
30
31
32
33
34
35
36
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;
}

Comments