Shortest Longest Increasing Subsequence Code

Question

The Challenge is to write the shortest implementation to find the Longest increasing subsequence .

Example : Let S be the sequence 1 5 7 1 8 4 3 5 [length of S = 8 ]

• We have 1 sub-sequence of length 0 [will consider it increasing]
  
• 6 sub-sequences of length 1 {1,5,7,8,4,3}[all of them are considered increasing]
  
• (7*8)/2 sub-sequences of length 2 [but we will remove duplicates], the increasing sub-seq are in strong black.
  {15,17,11,18,14,13,57,51,58,54,53,55,71,78,74,73,75,84,83,85,43,45,35}
  

[note that we only interested in strictly-increasing sub-sequences]

[you can't change the order of the elements inside the sequence , so there is no sub-sequence [37] in the example sequence]

• We have increasing sub-sequences of length 4 which is 1578 , but there's no sub-sequence of length 5 , so we consider the length of the longest increasing sub-sequence = 4.
  

Input:

a₁ a₂ ... a_N (The sequence)

all numbers are positive integers less than 10³
N <= 1000

Output:

One integer denoting the length of the longest increasing sub-sequence of the input sequence .

sample input(1)
1 2 4 2 5
sample output(1)
4

sample input(2)
1 5 7 1 8 4 3 5
sample output(2)
4

Your code should run in a timely manner please test your code on this case before submit it here (also the link contains my 290-byte c++11 solution )

You can either take the input from a file/stdin or as a function parameter and you can either print the output to a file/stdout or just return the value if you write a function

Score Board

1. Dennis CJam - 22
2. isaacg Pyth - 26
3. Howard GolfScript - 35
4. proud haskeller Haskell - 56
5. Ray Python 3 - 66
6. histocrat Ruby - 67
7. DLeh C# - 92
8. YosemiteMark Clojure - 94
9. faubiguy Python 3 - 113

Answer 1

Python 3, 66

Note that all numbers are in range [1, 999], we can use an array b to maintain the longest subsequence length ending with each number. b[x] = d means that the longest subsequence ending with x has length d. For each number from the input, we update the array using b[x] = max(b[:x]) + 1 and then we got the job done by taking max(b) finally.

The time complexity is O(n) O(m n), where m is always 1000 and n is the number of input elements.

def f(a):
 b=[0]*1000
 for x in a:b[x]=max(b[:x])+1
 return max(b)

Wow, looks like already ungolfed :) You can test it using stdin/stdout by adding a line:

print(f(map(int,input().split())))

Answer 2

Python - 113

a=[]
for i in map(int,input().split()):
 if not a or i>a[-1]:a+=[i]
 z=0
 while a[z]<i:z+=1
 a[z]=i
print(len(a))

Answer 3

Pyth, 26 29 33 39

J*]0^T3Fkyw=@JkheS:J0k)eSJ

Port of @ray's solution. Passes official tests. Now uses space-separated STDIN input, not function call.

Run as follows:

./pyth.py -c "J*]0^T3Fkyw=@JkheS:J0k)eSJ" <<< "1 5 7 2 8 4 3 5"
4

Explanation:

J*]0^T3                 J = [0]*10^3
Fkyw                    For k in space_sep(input()):
=@Jk                    J[k]=
heS:J0k                 max(J[0:k])+1
)                       end for
eSJ                     max(J)

---

Time unlimited:

Pyth, 18

L?eS,ytbhyf>Thbbb0

---

Technical note: I noticed a bug in my Pyth complier while writing this golf. L wasn't working. That's why there is a recent commit to the above git repository.

Answer 4

Clojure, 94 characters

Using @Ray's approach of updating results in a 1000-item vector:

(defn g[s](apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s)))

Per request, with print statement (will print answer and return nil). Input should be a vector (g [1 2 3]) or a list (g '(1 2 3)):

(defn g[s](prn(apply max(reduce #(assoc % %2(inc(apply max(take %2 %))))(into[](repeat 1e3 0))s))))

Answer 5

Haskell, 58 57 56 characters

(x:s)%v|v>x=x:s%v|0<1=v:s
_%v=[v]
l s=length$foldl(%)[]s

This uses an algorithm I saw once on the internet, but i can't find it. It takes an unnoticeable amount of time on the given test case on my computer with GHCi (probably would be even faster if it was compiled).

Answer 6

CJam, 22 bytes

1e3,q~{_2$<$0=(t}/$0=z

Try it online.

Example

$ cjam subsequence.cjam <<< '[2 1]'; echo
1
$ cjam subsequence.cjam <<< '[1 9 2 4 3 5]'; echo
4

The program prints 57 for this test case after 0.25 seconds.

How it works

I took the general idea from @Ray's answer.

1e3,    " Push the array [ 0 ... 999 ] (J).        ";
q~      " Read from STDIN and evaluate.            ";
{       " For each integer (I) of the input array: ";
  _2$<  " Push [ J[0] ... J[I - 1] ] (A).          ";
  $0=(  " Compute min(A) - 1.                      ";
  t     " Update J[I] with the value on the stack. ";
}/      "                                          ";
$0=     " Compute abs(min(J)).                     ";

Answer 7

GolfScript, 35 characters

~]]){1${~2$<*)}%1+$-1>[\+]+}/$-1=0=

An implementation working as a complete program with input on STDIN (without the length number given). The implementation is reasonable fast, even for longer inputs (try here).

Examples:

> 1 5 7 1 8 4 3 5
4

> 5 1 9 9 1 5
2

Answer 8

Ruby, 67

s=Hash.new{|s,a|f,*r=a
s[a]=f ?[1+s[r.select{|x|x>f}],s[r]].max: 0}

This runs in 30 seconds on the large input, does that count as a timely manner? :p

It's brute recursion, but with some memoization.

Answer 9

Bash+coreutils, 131 bytes

This solution fails horribly on the timely manner requirement, and is not even particularly short, but I liked that this sort of thing is at least theoretically possible in shell script, so I'm posting anyway. This runs with an eternity-inducing time complexity of O(2^n).

s=${1//,/,:\},\{}
a=`eval echo "{$s,:}"`
for s in $a;{
b="$(tr , \\n<<<$s|grep -v :)"
sort -nC<<<"$b"&&wc -w<<<$b
}|sort -nr|sed 1q

Input is a comma separated list passed as a single command-line argument:

$ time ./slisc.sh 1,5,7,1,8,4,3,5
4

real    0m1.240s
user    0m0.518s
sys 0m0.689s
$ 

Brace expansion is used to build the list of all possible subsequences.

• The first line replaces commas with ,:},{, which produces a string like 1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5
• The second line completes this string with braces, commas and semicolons to give this {1,:},{5,:},{7,:},{1,:},{8,:},{4,:},{3,:},{5,:}. This is a valid bash brace expansion, which when evaled with an echo produces this space-separated list 1,5,7,1,8,4,3,5 1,5,7,1,8,4,3,: 1,5,7,1,8,4,:,5 1,5,7,1,8,4,:,: ...
• by default, bash splits strings with whitespace, so we loop over each element of this list:
  • commas are replaced with newlines, then lines containing colons are removed, giving newline-separated lists for each possible subsequence
  • we then sort -C to test for increasing order, and if so, use wc -w to print the length of the list
• the resulting list of list lengths is sorted in reverse and the first value printed to give the longest increasing subsequence length.

Answer 10

C#, 172 92 chars

Nothing special, but I did it so I figured I might as well submit it.

int a(int[] j){int c=2,m=2,i=1;for(;++i<j.Length;){c=j[i]>j[i-1]?c+1:2;m=c>m?c:m;}return m;}

Thanks Armin and Bob for their improvements!

Answer 11

Stax, 21 bytes

ë/NS7Γ╥╚┌{1╤╒¬è¶²╢╦┌☼

Run and debug it

This has two test cases, one of which is the 1000-element case. It runs that one in 24 seconds on my machine. It uses the classic dynamic programming approach for this type of problem.

Answer 12

J, 19 bytes

[:#]`I.`[} ::,~/@|.

Try it online!

Runs in O(n log n), using a modified patience sort since only the length, not the actual subsequence, is needed.

Explanation

[:#]`I.`[} ::,~/@|.  Input: array
                 |.  Reverse
               /     Reduce right-to-left
     I.                Find the index to insert while keeping it sorted
                       (uses binary search)
         }             Amend the current search array at that index with the next value
           ::          If error (when the index is not found)
             ,           Append the value at the end
 #                   Length of that array

Answer 13

J 34

Note that I read standard input as well.

>./;+/@:*&.>(<*>.)/\&.><\.".1!:1]3

Without reading standard input, the meat is 26 characters.

>./;+/@:*&.>(<*>.)/\&.><\.

Just noticed mine runs slow for large input, oh well.

Answer 14

C++ (gcc), 129 bytes

int f(int*a,int n){int l[n]{},i=n,j,m=0;for(;i--;m=l[i]>m?l[i]:m)for(j=n;--j>i;)if(a[i]<a[j]&&l[i]<l[j]+1)l[i]=l[j]+1;return++m;}

Try it online!

Answer 15

C# (.NET Core), 155 bytes

Used an array to compute the longest increasing subsequence ending at each position in the input array (dynamic programming), then returned the largest value. For example, the computed array for input [1,5,7,1,8,4,3,5] would be [1,2,3,1,4,2,2,3], and the largest value 4 is returned.

int b(int[]x){int l=x.Length,r=1,i=0,j,c;var a=new int[l];a[0]=1;while(++i<l)for(j=0;j<i;j++){c=x[j]<x[i]?a[j]+1:1;a[i]=a[i]<c?c:a[i];r=r<c?c:r;}return r;}

Try it online!

Answer 16

Wolfram Language (Mathematica), 38 bytes

Length@LongestOrderedSequence[#,Less]&

Try it online!

There is of course a Mathematica built-in for finding longest ordered sequences. Its name is very long: it makes up more than half the solution, and I won't be surprised if someone out-golfs this solution.