# 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