Longest Increasing Subsequence
+1
−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.
+1
−0
[Haskell], 37 bytes f(h …
5mo ago
+1
−0
[JavaScript (Node.js)], 70 56 …
5mo ago
+0
−0
Japt `-h`, 12 bytes à k …
5mo ago
+0
−0
[Husk], 10 bytes L►LfΛo …
5mo ago
4 answers
+1
−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 comments
+1
−0
+0
−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
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 5 months ago
@Lundin No negative numbers, limit goes up to the int range in your language of choice — Quintec 5 months ago