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
| // @Title: 俄罗斯套娃信封问题 (Russian Doll Envelopes)
// @Author: 15816537946@163.com
// @Date: 2021-03-04 23:22:20
// @Runtime: 344 ms
// @Memory: 6.5 MB
func maxEnvelopes(envelopes [][]int) int {
n := len(envelopes)
if n == 0 {
return 0
}
sort.Slice(envelopes, func(i, j int) bool {
a, b := envelopes[i], envelopes[j]
return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
})
f := make([]int, n)
for i := range f {
f[i] = 1
}
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if envelopes[j][1] < envelopes[i][1] {
f[i] = max(f[i], f[j]+1)
}
}
}
return max(f...)
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}
|