求最长增加子数列是一道经典算法题，其动态规划解法最简单，但是时间复杂度是O(n²)。stackoverflow上有一个O(nlogn)解法，很是巧妙：
Now the improvement happens at the second loop, basically, you can improve the speed by using binary search. Besides the array dp[], let’s have another array c[], c is pretty special, c[i] means: the minimum value of the last element of the longest increasing sequence whose length is i.
sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
if( array[i] < c[1] ) {
c[1] = array[i]; /*you have to update the minimum value right now*/
dp[i] = 1;
}
else if( array[i] > c[sz] ) {
c[sz+1] = array[i];
dp[i] = sz+1;
sz++;
}
else {
int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
c[k] = array[i];
dp[i] = k;
}
}
关键是理解这个c数组，其下标用来表示增加子数列的长度，而值则是这个长度的增加子数列中结尾元素最小的值。比如有两个相同长度的增加子数列：1,2,3和1,2,5，则c[3]的值为3，因为一旦将来有4出现，就可以把1,2,3扩展为1,2,3,4，而无法再把1,2,5扩展。完整的Go程序如下：
package main
import (
"fmt"
"os"
)
func bSearch(array []int, start int, end int, value int) int {
for start <= end {
mid := start + (end-start)/2
if array[mid] == value {
return mid
} else if array[mid] < value {
if mid+1 <= end && array[mid+1] > value {
return mid+1
} else {
start = mid+1
}
} else {
if mid-1 >= start && array[mid-1] < value {
return mid
} else {
end = mid-1
}
}
}
return start
}
func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var num int
_, err := fmt.Scan(&num)
if err != nil || num == 0{
os.Exit(1)
}
s := make([]int, num)
m := make([]int, num)
e := make([]int, num+1)
for i := 0; i < num; i++ {
_, err := fmt.Scan(&s[i])
if err != nil {
os.Exit(1)
}
}
m[0] = 1
max := m[0]
e[1] = s[0]
for i := 1; i < num; i++ {
if s[i] < e[1] {
e[1] = s[i]
m[i] = 1
} else if s[i] > e[max] {
max++
e[max] = s[i]
m[i] = max
} else {
k := bSearch(e, 1, max, s[i])
e[k] = s[i]
m[i] = k
}
}
fmt.Println(max)
}