Fix low-coverage tiles counting toward min coverage threshold.
[lightning.git] / 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 }