X-Git-Url: https://git.arvados.org/lightning.git/blobdiff_plain/8848abc2ee9635bec7b5ad6239eb17481df4f061..04f618563a9603f6e56e5d6480f263c09e0cf89f:/lis.go

diff --git a/lis.go b/lis.go
new file mode 100644
index 0000000000..2103af07bd
--- /dev/null
+++ b/lis.go
@@ -0,0 +1,34 @@
+package main
+
+func longestIncreasingSubsequence(srclen int, X func(int) int) []int {
+	if srclen == 0 {
+		return nil
+	}
+	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]
+	P := make([]int, srclen)   // P[k] == index in X of predecessor of X[k] in longest increasing subsequence ending at X[k]
+	L := 0                     // length of longest increasing subsequence found so far
+	for i := range P {
+		lo, hi := 1, L
+		for lo <= hi {
+			mid := (lo + hi + 1) / 2
+			if X(M[mid]) < X(i) {
+				lo = mid + 1
+			} else {
+				hi = mid - 1
+			}
+		}
+		newL := lo
+		if i > 0 {
+			P[i] = M[newL-1]
+		}
+		M[newL] = i
+		if newL > L {
+			L = newL
+		}
+	}
+	ret := make([]int, L)
+	for k, i := M[L], len(ret)-1; i >= 0; k, i = P[k], i-1 {
+		ret[i] = k
+	}
+	return ret
+}