题解 | #拦截导弹#

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)
}