Longest Increasing Subsequence
+3
−0
Given an array of numbers, output the length of the longest increasing (not necessarily contiguous) subsequence. It is guaranteed that there are no duplicates in the array. For example, if the input was [1, 5, 2, 4], the answer would be 3 for the subsequence [1, 2, 4].
More I/O Examples
Input -> Output
[1] -> 1
[2, 1] -> 1
[1, 2, 3] -> 3
[5, 2, 1, 4, 3] -> 2
[7, 1, 8, 10, 3, 9, 5, 4, 6, 2] -> 4
This is code-golf, so shortest code wins.
+2
−0
[Haskell], 37 bytes f(h …
4y ago
+2
−0
[JavaScript (Node.js)], 70 56 …
4y ago
+1
−0
Japt `-h`, 12 bytes à k …
3y ago
+1
−0
[Husk], 10 bytes L►LfΛo …
4y ago
4 answers
+2
−0
+2
−0
JavaScript (Node.js), 70 56 bytes
f=([a,...b],c=f)=>1/a?Math.max(f(b,c),[a]>c&&1+f(b,a)):0
0 comment threads
+1
−0
Japt -h, 12 bytes
à kÈäÎdÄÃmÊñ
à kÈäÎdÄÃmÊñ :Implicit input of array
à :Combinations
k :Remove elements that return true
È :When passed through the following function
ä : Consecutive pairs
Î : Reduced by the sign of their difference
d : Are any truthy (not zero)
Ä : When 1 is added to them
à :End filter
m :Map
Ê : Length
ñ :Sort
:Implicit output of last element
0 comment threads
+1
−0
Husk, 10 bytes
L►LfΛo<0-Ṗ
Explanation
L►LfΛo<0-Ṗ
Ṗ power set of input
f get elements which match the following:
Λo - all pairwise differences
<0 are negative
►L max by length
L length of that
1 comment thread