lis.go

   1 package main
   2
   3 func longestIncreasingSubsequence(srclen int, X func(int) int) []int {
   4         if srclen == 0 {
   5                 return nil
   6         }
   7         M := make([]int, srclen+1) // M[j] == index into X such that X[M[j]] is the smallest X[k] where k<=i and an increasing subsequence with length j ends at X[k]
   8         P := make([]int, srclen)   // P[k] == index in X of predecessor of X[k] in longest increasing subsequence ending at X[k]
   9         L := 0                     // length of longest increasing subsequence found so far
  10         for i := range P {
  11                 lo, hi := 1, L
  12                 for lo <= hi {
  13                         mid := (lo + hi + 1) / 2
  14                         if X(M[mid]) < X(i) {
  15                                 lo = mid + 1
  16                         } else {
  17                                 hi = mid - 1
  18                         }
  19                 }
  20                 newL := lo
  21                 if i > 0 {
  22                         P[i] = M[newL-1]
  23                 }
  24                 M[newL] = i
  25                 if newL > L {
  26                         L = newL
  27                 }
  28         }
  29         ret := make([]int, L)
  30         for k, i := M[L], len(ret)-1; i >= 0; k, i = P[k], i-1 {
  31                 ret[i] = k
  32         }
  33         return ret
  34 }