package main import ( "bufio" "fmt" "os" "sort" "strconv" "strings" ) /* * 二维数组排序 */ func solution(envelopes [][]int) int { if len(envelopes) == 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]) }) //计算最长递增子列:只看第二个元素的递增(严格递增) dp := make([]int, len(envelopes)) for i := range dp { dp[i] = 1 } //最差时,也有一个信封 res := 1 for i := 1; i < len(envelopes); i++ { for j := 0; j < i; j++ { if envelopes[j][1] < envelopes[i][1] { dp[i] = max(dp[i], dp[j]+1) } res = max(res, dp[i]) } } return res } func max(a, b int) int { if a > b { return a } return b } /* * 9 3 4 2 3 4 5 1 3 2 2 3 6 1 2 3 2 2 4 结果 4 从里到外是 (1,2) (2,3) (3,4) (4,5) */ func main() { var num int fmt.Scanln(&num) arr := make([][]int, num) scanner := bufio.NewScanner(os.Stdin) for i := 0; i < num; i++ { scanner.Scan() str := scanner.Text() strs := strings.Split(str, " ") tmp := make([]int, 0) for _, val := range strs { ele, _ := strconv.Atoi(val) tmp = append(tmp, ele) } arr[i] = tmp } fmt.Println(solution(arr)) }