current community

your communities

more stack exchange communities

Stack Exchange
tour help
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.
up vote 7 down vote favorite

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]
  • 8 sub-sequences of length 1 {1,5,7,1,8,4,3,5}[all of them are considered increasing]
  • (7*8)/2 sub-sequences of length 2 , the increasing sub-seq are in strong black.
    {15,17,11,18,14,13,15,57,51,58,54,53,55,71,78,74,73,75,18,14,13,15,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 function parameters(no need to add the size parameter,if you want) and you can either print the output to a file/stdout or just return the value if you write a function

share|improve this question
    
"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 6 hours ago

9 Answers 9

up vote 4 down vote

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 12 hours ago
    
@Howard It's O(1000 n) and 1000 is a constant. You can also think it as O(m n). –  Ray 12 hours ago
2  
With such argument the whole discussion is useless because on limited input the complexity is always O(1) ;-) –  Howard 12 hours ago
    
@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 12 hours ago
    
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 9 hours ago
up vote 3 down vote

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 12 hours ago
    
@Mostafa36a2 The word "accepted" has another meaning on this site. I think what you mean is "acceptable". –  Ray 12 hours ago
    
Sorry , yes I meant acceptable ,too early to choose the Accepted one . –  Mostafa 36a2 12 hours ago
    
With the line a+=[i]*(a==[]or i>a[-1]);z=0 and printing len(a) (without brackets) you can save 4 characters. –  Falko 9 hours ago
up vote 3 down vote

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 13 hours ago
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 13 hours ago
    
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 13 hours ago
    
@Mostafa36a2 Got it, I just noticed that line. I'll work on an improvement. –  isaacg 13 hours ago
1  
Sorry I see the update now , please try this case and tell me if it works . –  Mostafa 36a2 12 hours ago
up vote 2 down vote

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 10 hours ago
up vote 2 down vote

Haskell, 58 57 characters

(x:s)%v|v<=x=v:s|0<1=x:s%v
_%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 7 hours ago
    
@Ray you're right –  proud haskeller 7 hours ago
up vote 1 down vote

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
up vote 0 down vote

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 13 hours ago
    
please try the input in this link –  Mostafa 36a2 12 hours ago
    
@Mostafa36a2 I did already (see comment before). After 5 seconds it returns 58. –  Howard 12 hours ago
    
this is another one , it should return 57 , so if your code did return 57 then it's Accepted :) Congratulations –  Mostafa 36a2 12 hours ago
    
@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 12 hours ago
up vote 0 down vote

C#, 172 chars

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

int a(string s){var j=s.Split(' ').Select(t => int.Parse(t)).ToArray();int c=2,m=2;for(var i=0;i<j.Length;i++){if(i>0){if(j[i]>j[i-1]){c++;if(c>m)m=c;}else c=2;}}return m;}
share|improve this answer
up vote 0 down vote

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