AcWing 896. GoLang - Longest Increasing Subsequence - DP 1D with Binary Search
原题链接
中等
作者:
idiotleon
,
2020-12-28 11:05:07
,
所有人可见
,
阅读 450
package main
import "fmt"
const N = 1e5 + 7
func main(){
nums := make([]int, N)
dp := make([]int, N)
var n int
fmt.Scanf("%d", &n)
for i := 0; i < n; i++ {
fmt.Scan(&nums[i])
}
len := 0
for idx, val := range nums{
lo, hi := 0, len
for lo < hi{
mid := lo + hi + 1 >> 1
if dp[mid] < val {
lo = mid
}else{
hi = mid - 1
}
}
if len < hi + 1{
len = hi + 1
}
dp[hi + 1] = nums[idx]
}
fmt.Println(len)
}