Longest Increasing Subsequence
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.
[Haskell], 37 bytes f(h …
4y ago
[JavaScript (Node.js)], 70 56 …
4y ago
Japt `-h`, 12 bytes à k …
3y ago
[Husk], 10 bytes L►LfΛo …
4y ago
4 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
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
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
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 comment thread