Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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:

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
  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
share|improve this question
1  
"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 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 at 8:18
1  
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? –  sudo Aug 24 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 at 9:09

11 Answers 11

up vote 2 down vote accepted

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)).                     ";
share|improve this answer

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())))
share|improve this answer
    
for x in a: max(b) looks pretty much O(n^2). –  Howard Aug 21 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 at 13:45
2  
With such argument the whole discussion is useless because on limited input the complexity is always O(1) ;-) –  Howard Aug 21 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 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 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))
share|improve this answer
    
Accepted solution. Your code have been tested here and here. –  Mostafa 36a2 Aug 21 at 13:16
    
@Mostafa36a2 The word "accepted" has another meaning on this site. I think what you mean is "acceptable". –  Ray Aug 21 at 13:40
    
Sorry , yes I meant acceptable ,too early to choose the Accepted one . –  Mostafa 36a2 Aug 21 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 at 16:09

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.

share|improve this answer
    
your code doesn't run in a timely manner for a case with large list (say 100 element) –  Mostafa 36a2 Aug 21 at 12:32
3  
@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 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 at 12:45
    
@Mostafa36a2 Got it, I just noticed that line. I'll work on an improvement. –  isaacg Aug 21 at 12:46
1  
Sorry I see the update now , please try this case and tell me if it works . –  Mostafa 36a2 Aug 21 at 13:21

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

share|improve this answer
    
The algorithm you mentioned is the same as that used by @faubiguy. –  Ray Aug 21 at 18:17
    
@Ray you're right –  proud haskeller Aug 21 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
share|improve this answer
1  
@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 at 13:07
    
please try the input in this link –  Mostafa 36a2 Aug 21 at 13:22
    
@Mostafa36a2 I did already (see comment before). After 5 seconds it returns 58. –  Howard Aug 21 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 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 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.

share|improve this answer
1  
Yes , this is a timely manner :) –  Mostafa 36a2 Aug 21 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!

share|improve this answer
1  
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 at 9:51
2  
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 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 at 10:15
1  
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 at 10:21
2  
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 at 10:36

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))))
share|improve this answer
    
can you add the print statement to make it testable ? It will not be counted in the score. –  Mostafa 36a2 Aug 22 at 8:15
1  
Updated. I've run it on both your large examples, and got 58 and 57 as expected. –  YosemiteMark Aug 22 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 at 16:04

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.
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.