18 lines
570 B
Text
18 lines
570 B
Text
def lis:
|
|
|
|
# Helper function:
|
|
# given a stream, produce an array of the items in reverse order:
|
|
def reverse(stream): reduce stream as $i ([]; [$i] + .);
|
|
|
|
# put the items into increasing piles using the structure:
|
|
# NODE = {"val": value, "back": NODE}
|
|
reduce .[] as $x
|
|
( []; # array of NODE
|
|
# binary search for the appropriate pile
|
|
(map(.val) | bsearch($x)) as $i
|
|
| setpath([$i];
|
|
{"val": $x,
|
|
"back": (if $i > 0 then .[$i-1] else null end) })
|
|
)
|
|
| .[length - 1]
|
|
| reverse( recurse(.back) | .val ) ;
|