![](https://img.shields.io/badge/分数-1849-4051B5?style=flat-square)
题目描述
给你一个整数数组 nums
和一个 非负 整数 k
。如果一个整数序列 seq
满足在范围下标范围 [0, seq.length - 2]
中存在 不超过 k
个下标 i
满足 seq[i] != seq[i + 1]
,那么我们称这个整数序列为 好 序列。
请你返回 nums
中 好 子序列 的最长长度
示例 1:
输入:nums = [1,2,1,1,3], k = 2
输出:4
解释:
最长好子序列为 [1,2,1,1,3]
。
示例 2:
输入:nums = [1,2,3,4,5,1], k = 0
输出:2
解释:
最长好子序列为 [1,2,3,4,5,1]
。
提示:
1 <= nums.length <= 500
1 <= nums[i] <= 109
0 <= k <= min(nums.length, 25)
解法
方法一:动态规划
我们定义 $f[i][h]$ 表示以 $nums[i]$ 结尾,且有不超过 $h$ 个下标满足条件的最长好子序列的长度。初始时 $f[i][h] = 1$。答案为 $\max(f[i][k])$,其中 $0 \le i < n$。
我们考虑如何计算 $f[i][h]$。我们可以枚举 $0 \le j < i$,如果 $nums[i] = nums[j]$,那么 $f[i][h] = \max(f[i][h], f[j][h] + 1)$;否则如果 $h > 0$,那么 $f[i][h] = \max(f[i][h], f[j][h - 1] + 1)$。即:
$$
f[i][h]=
\begin{cases}
\max(f[i][h], f[j][h] + 1), & \textit{if } nums[i] = nums[j], \
\max(f[i][h], f[j][h - 1] + 1), & \textit{if } h > 0.
\end{cases}
$$
最终答案为 $\max(f[i][k])$,其中 $0 \le i < n$。
时间复杂度 $O(n^2 \times k)$,空间复杂度 $O(n \times k)$。其中 $n$ 是数组 nums
的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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;
}
}
|
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:
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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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;
}
|
方法二:动态规划优化
根据方法一的状态转移方程,如果 $nums[i] = nums[j]$,那么我们只需要获取 $f[j][h]$ 的最大值,我们可以用一个长度为 $k + 1$ 的数组 $mp$ 来维护。如果 $nums[i] \neq nums[j]$,我们需要记录 $f[j][h - 1]$ 的最大值对应的 $nums[j]$,最大值和次大值,我们可以用一个长度为 $k + 1$ 的数组 $g$ 来维护。
时间复杂度 $O(n \times k)$,空间复杂度 $O(n \times k)$。其中 $n$ 是数组 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;
}
|