题目描述
最长上升子序列,长度 = len(a) , 其中一个序列是 res
a 的 第0 个数到第flag 个数在原数列第顺序是递增的
len(a) 是正确的, res 没找到测试的地方,试了几个样例没问题
样例
package main
import "fmt"
var n,x int
var a,res []int
func main(){
fmt.Scan(&n)
var flag int = -1
a = make([]int,0)
for i:=0;i<n;i++{
fmt.Scan(&x)
if len(a)==0 || a[len(a)-1]<x{
if flag + 1 ==len(a){
flag++
}
a=append(a,x)
res = append(res,x)
continue
}
index := find(0,len(a)-1,x)
if a[index]==x{
continue
}
a[index]=x
if flag + 1 == index {
flag++
}else if flag > index{
flag = index
}
if flag ==len(a)-1{
copy(res,a)
}
}
fmt.Println(len(a))
// fmt.Println(a,res)
}
func find(l,r,num int)int{
if l>=r{
if a[r]>=num{
return r
}
return r+1
}
mid:=(l+r)>>1
if a[mid]<num{
return find(mid+1,r,num)
}
return find(l,mid,num)
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla