lis.go

   1 // Copyright (C) The Lightning Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: AGPL-3.0
   4
   5 package lightning
   6
   7 func longestIncreasingSubsequence(srclen int, X func(int) int) []int {
   8         if srclen == 0 {
   9                 return nil
  10         }
  11         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]
  12         P := make([]int, srclen)   // P[k] == index in X of predecessor of X[k] in longest increasing subsequence ending at X[k]
  13         L := 0                     // length of longest increasing subsequence found so far
  14         for i := range P {
  15                 lo, hi := 1, L
  16                 for lo <= hi {
  17                         mid := (lo + hi + 1) / 2
  18                         if X(M[mid]) < X(i) {
  19                                 lo = mid + 1
  20                         } else {
  21                                 hi = mid - 1
  22                         }
  23                 }
  24                 newL := lo
  25                 if i > 0 {
  26                         P[i] = M[newL-1]
  27                 }
  28                 M[newL] = i
  29                 if newL > L {
  30                         L = newL
  31                 }
  32         }
  33         ret := make([]int, L)
  34         for k, i := M[L], len(ret)-1; i >= 0; k, i = P[k], i-1 {
  35                 ret[i] = k
  36         }
  37         return ret
  38 }