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 …
~2mo ago
[JavaScript (Node.js)], 70 56 …
~2mo ago
Japt `-h`, 12 bytes à k …
~1mo ago
[Husk], 10 bytes L►LfΛo …
~2mo ago
4 answers
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 comments
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
2 comments
It prints 2 for [7,1,9,3,8,5,4,6,2], but the subsequence 1,3,5,6 has length 4.
gotcha, will change it.
2 comments
What's the upper limit to number of items supported and the values themselves? Does it need to cover negative numbers? — Lundin about 2 months ago
@Lundin No negative numbers, limit goes up to the int range in your language of choice — Quintec about 2 months ago