题目连接: 896. 最长上升子序列 II
前情提要
这是 895. 最长上升子序列 的数据强化版,用原来的代码只会TLE
要怎么办呢?
一种特别的DP用法
dp[i]
原本表示在数组下标为i之前上升子序列的长度,如果将其换成下标是增长序列的长度且单调递增,在该位置放的是该长度增长序列的结尾的值最小值。在这样的单调递增上,就可以用二分查找来定arr[i]该到哪个dp[i]
还是看不懂的话,直接看看运行结果:
代码
package main
import "fmt"
func cal(N int, arr []int) int {
var (
len = 0
max = func(i, j int) int { if i > j { return i }; return j }
dp = make([]int, N + 1)
)
for i := 1; i <= N; i++ {
left, right := 0, len
for left < right {
mid := (left + right + 1) >> 1
if dp[mid] < arr[i] {
left = mid
} else {
right = mid - 1
}
}
len = max(len, right + 1)
dp[right + 1] = arr[i]
}
return len
}
func main() {
var (
ans int
N, tmp int
arr = []int{0}
)
fmt.Scanf("%d", &N)
for i := 1; i <= N; i++ {
fmt.Scanf("%d", &tmp)
arr = append(arr, tmp)
}
ans = cal(N, arr)
fmt.Println(ans)
}