package main import ( "bufio" "fmt" "os" "strconv" "strings" ) /* * 本质: 1、求解最长的递减子列长度(非严格递减,即:可以包含=) 2、Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度(严格递增,即:不包含=) */ func solution(arr []int) (int, int) { incrementDp := make([]int, len(arr)) decrementDp := make([]int, len(arr)) for i := 0; i < len(arr); i++ { incrementDp[i] = 1 decrementDp[i] = 1 } maxIncrement := 0 maxDecrement := 0 for i := 1; i < len(arr); i++ { for j := 0; j < i; j++ { //计算1 if arr[i] <= arr[j] { decrementDp[i] = max(decrementDp[i], decrementDp[j]+1) } maxDecrement = max(maxDecrement, decrementDp[i]) //计算2 if arr[i] > arr[j] { incrementDp[i] = max(incrementDp[i], incrementDp[j]+1) } maxIncrement = max(maxIncrement, incrementDp[i]) } } return maxDecrement, maxIncrement } func max(a, b int) int { if a > b { return a } return b } /* * 8 389 207 155 300 299 170 158 65 结果 6 2 */ func main() { var count int fmt.Scanln(&count) arr := make([]int, count) scanner := bufio.NewScanner(os.Stdin) scanner.Scan() str := scanner.Text() strs := strings.Split(str, " ") for i, val := range strs { ele, _ := strconv.Atoi(val) arr[i] = ele } maxDecrement, maxIncrement := solution(arr) fmt.Println(maxDecrement) fmt.Println(maxIncrement) }