# Shortest Longest Increasing Subsequence Code

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  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:

a1 a2 ... aN (The sequence)

all numbers are positive integers less than 103
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
5. Ray Python 3 - 66
6. histocrat Ruby - 67
7. DLeh C# - 92
8. YosemiteMark Clojure - 94
9. faubiguy Python 3 - 113
• "We have 1 sub-sequence of length 0 [will consider it increasing]", Well technically you have an infinite number of 0-length sub-sequences :) – Cruncher Aug 21 '14 at 19:17
• Actually , I have to change the statement so that all the "Sets" must remove the duplicates , e.g. {1,5,7,1,8,4,3,5} should be {1,5,7,8,4,3} and then we can say that there is 1 0-length subsequence in the "Set" . thanks – Mostafa 36a2 Aug 22 '14 at 8:18
• For functions, should we count the bytes of the outer function (function f(){...}) or the inner function (just ...)? If we count outer functions, are anonymous functions allowed? – Dennis Aug 24 '14 at 3:06
• We count the outer function , and anonymous functions are allowed , But don't miss to provide a testable version (complete version with the input/output handling) – Mostafa 36a2 Aug 25 '14 at 9:09

# CJam, 22 bytes

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 ... J[I - 1] ] (A).          ";
$0=( " Compute min(A) - 1. "; t " Update J[I] with the value on the stack. "; }/ " ";$0=     " Compute abs(min(J)).                     ";


# 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=*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())))

• for x in a: max(b) looks pretty much O(n^2). – Howard Aug 21 '14 at 13:41
• @Howard It's O(1000 n) and 1000 is a constant. You can also think it as O(m n). – Ray Aug 21 '14 at 13:45
• With such argument the whole discussion is useless because on limited input the complexity is always O(1) ;-) – Howard Aug 21 '14 at 13:47
• @Howard I come from the ACM-ICPC world and this is somewhat a convention there. You can think it as O(m n). It's still different from O(n^2). Anyway, the time it cost will be less than the interpreter start-up time so I think it's fast enough. – Ray Aug 21 '14 at 13:53
• Impressively short algorithm! I can only spot one character (at least when switching to Python 2): You can print the result. print is shorter than return. – Falko Aug 21 '14 at 16:19

# 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))

• Accepted solution. Your code have been tested here and here. – Mostafa 36a2 Aug 21 '14 at 13:16
• @Mostafa36a2 The word "accepted" has another meaning on this site. I think what you mean is "acceptable". – Ray Aug 21 '14 at 13:40
• Sorry , yes I meant acceptable ,too early to choose the Accepted one . – Mostafa 36a2 Aug 21 '14 at 13:47
• With the line a+=[i]*(a==[]or i>a[-1]);z=0 and printing len(a) (without brackets) you can save 4 characters. – Falko Aug 21 '14 at 16:09

# Pyth, 26 293339

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 = *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.

• your code doesn't run in a timely manner for a case with large list (say 100 element) – Mostafa 36a2 Aug 21 '14 at 12:32
• @Mostafa36a2 If you'd like to make runtime a requirement, please say so in the question, and add a test case or two. If it's just a comment, then I agree, it's pretty slow. – isaacg Aug 21 '14 at 12:40
• Sorry but I've mentioned that is not the runtime but at least a [timely manner] , no problem if the code takes 10-20 minutes or even an hour , but the O(2^n) solutions will never give the result during our long life. – Mostafa 36a2 Aug 21 '14 at 12:45
• @Mostafa36a2 Got it, I just noticed that line. I'll work on an improvement. – isaacg Aug 21 '14 at 12:46
• Sorry I see the update now , please try this case and tell me if it works . – Mostafa 36a2 Aug 21 '14 at 13:21

### 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))))

• can you add the print statement to make it testable ? It will not be counted in the score. – Mostafa 36a2 Aug 22 '14 at 8:15
• Updated. I've run it on both your large examples, and got 58 and 57 as expected. – YosemiteMark Aug 22 '14 at 15:25
• I think you still need to call the function :p , but if you've tested it then that is enough . – Mostafa 36a2 Aug 22 '14 at 16:04

(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). • The algorithm you mentioned is the same as that used by @faubiguy. – Ray Aug 21 '14 at 18:17 • @Ray you're right – proud haskeller Aug 21 '14 at 18:20 ### 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  • @MartinBüttner It takes about 5 seconds for 1000 numbers on my computer. Assuming $ is O(n log n) the algorithm is O(n^2 log n). – Howard Aug 21 '14 at 13:07
• please try the input in this link – Mostafa 36a2 Aug 21 '14 at 13:22
• @Mostafa36a2 I did already (see comment before). After 5 seconds it returns 58. – Howard Aug 21 '14 at 13:24
• this is another one , it should return 57 , so if your code did return 57 then it's Accepted :) Congratulations – Mostafa 36a2 Aug 21 '14 at 13:26
• @Mostafa36a2 Ah, now I see those are two distinct test cases. Yes, your second link returns 57 as does my solution on this input. – Howard Aug 21 '14 at 13:44

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

• Yes , this is a timely manner :) – Mostafa 36a2 Aug 21 '14 at 15:15

### 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!

• you can change your parameter to int[] and then you'd have less characters because you wouldn't need to cast string to int – Armin Aug 22 '14 at 9:51
• The spaces around => are unnecessary. You can also move the i=0 declaration outside the for loop, to int c=2,m=2,i=0;for(;. You can also drop the braces around the for body, since you only have a single statement in there. – Bob Aug 22 '14 at 10:09
• And c++;if(c>m)m=c; can be m=c++>m?m:c;, and you can again drop the braces around that. – Bob Aug 22 '14 at 10:15
• In fact, you can also discard the if(i>0) check by making the for loop start at 1. You can further shorten the int c=2,m=2,i=0;for(;i<j.Length;i++)if(i>0) suggested earlier into int c=2,m=2,i=0;for(;i++<j.Length;). That entire section could be converted to int c=2,m=2,i=0;for(;i++<j.Length;){c=j[i]>j[i-1]?c+1:2;m=c>m?m:c;} (using another ternary to replace the last remaining if - rule of thumb is ternaries are shorter if your if body is simply an assignment. – Bob Aug 22 '14 at 10:21
• Sorry - typo in my previous comment, m=c>m?m:c should be m=c>m?c:m. And if you add in @Armin's suggestion, you get 92 bytes, almost halving the size! int a(int[] j){int c=2,m=2,i=0;for(;i++<j.Length;){c=j[i]>j[i-1]?c+1:2;m=c>m?c:m;}return m;} – Bob Aug 22 '14 at 10:36

# 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
,           Append the value at the end
#                   Length of that array


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

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

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

# 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!

# 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=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!

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