求解最长增加子数列

求最长增加子数列是一道经典算法题，其动态规划解法最简单，但是时间复杂度是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)
}