Longest Increasing Subsequence

+2

−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.

code-golf

posted 8 months ago

CC BY-SA 4.0

Quintec‭ ☖

1459 reputation 15 32 154 39

Permalink History

needs author's attention

This question is off-topic or cannot be reasonably answered in its current form and needs revision by its author.

This flag will be added as a comment to this post's feedback thread.

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

+1

−0

[Haskell], 37 bytes f(h …

8mo ago

+1

−0

[JavaScript (Node.js)], 70 56 …

8mo ago

+0

−0

Japt `-h`, 12 bytes à k …

~1mo ago

+0

−0

[Husk], 10 bytes L►LfΛo …

8mo ago

1 comment thread

General comments (2 comments)

+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

Try it online!

posted 8 months ago

CC0

8mo ago

Hakerh400‭

801 reputation 3 29 80 46

Permalink History

0 comment threads

+1

−0

Haskell, 37 bytes

f(h:t)=max(1+f[x|x<-t,x>h])$f t
f _=0

Try it online!

posted 8 months ago

CC BY-SA 4.0

xnor‭

211 reputation 0 7 21 16

Permalink History

0 comment threads

+0

−0

Japt `-h`, 12 bytes

à kÈäÎdÄÃmÊñ

Try it

à 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

posted 8 months ago

CC BY-SA 4.0

~1mo ago

Shaggy‭

401 reputation 0 38 40 44

Permalink History

0 comment threads

+0

−0

Husk, 10 bytes

L►LfΛo<0-Ṗ

Try it online!

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

posted 8 months ago

CC BY-SA 4.0

8mo ago

Razetime‭

1424 reputation 24 37 145 52

Permalink History

1 comment thread

General comments (2 comments)

Communities

Longest Increasing Subsequence

More I/O Examples

1 comment thread

4 answers

JavaScript (Node.js), 70 56 bytes

0 comment threads

Haskell, 37 bytes

0 comment threads

Japt `-h`, 12 bytes

0 comment threads

Husk, 10 bytes

Explanation

1 comment thread

Communities

Longest Increasing Subsequence

More I/O Examples

1 comment thread

4 answers

JavaScript (Node.js), 70 56 bytes

0 comment threads

Haskell, 37 bytes

0 comment threads

Japt -h, 12 bytes

0 comment threads

Husk, 10 bytes

Explanation

1 comment thread

Japt `-h`, 12 bytes