NIH的博后工资标准够请到什么样的人?# Biology - 生物学
l*r
1 楼
一个任意的数组,找出一个严格单调递增的最长子序列。
例如:{3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8}
output: 0, 1, 2, 4, 5, 6, 8
但是 {3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8}
output: 0, 1, 2, 4, 9, 10, 15
网上随便搜了一下:很简洁巧妙的算法,能在O(N log N)时间和O(N)空间做出来!方法
就是始终保持一个单增的序列,然后新来的数如果比当前最大还大就append在后面,否
则在单增序列里面做binary search,替换相应位置的数。
没看懂这个替换怎么个做法?上面的两个例子里面,遇到5的时候,怎么替换呢?
例如:{3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8}
output: 0, 1, 2, 4, 5, 6, 8
但是 {3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8}
output: 0, 1, 2, 4, 9, 10, 15
网上随便搜了一下:很简洁巧妙的算法,能在O(N log N)时间和O(N)空间做出来!方法
就是始终保持一个单增的序列,然后新来的数如果比当前最大还大就append在后面,否
则在单增序列里面做binary search,替换相应位置的数。
没看懂这个替换怎么个做法?上面的两个例子里面,遇到5的时候,怎么替换呢?