12
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ "We have 1 sub-sequence of length 0 [will consider it increasing]", Well technically you have an infinite number of 0-length sub-sequences :) \$\endgroup\$
    – Cruncher
    Aug 21, 2014 at 19:17
  • \$\begingroup\$ 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 \$\endgroup\$ Aug 22, 2014 at 8:18
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Dennis
    Aug 24, 2014 at 3:06
  • \$\begingroup\$ 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) \$\endgroup\$ Aug 25, 2014 at 9:09

16 Answers 16

5
\$\begingroup\$

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())))
\$\endgroup\$
8
  • \$\begingroup\$ for x in a: max(b) looks pretty much O(n^2). \$\endgroup\$
    – Howard
    Aug 21, 2014 at 13:41
  • \$\begingroup\$ @Howard It's O(1000 n) and 1000 is a constant. You can also think it as O(m n). \$\endgroup\$
    – Ray
    Aug 21, 2014 at 13:45
  • 3
    \$\begingroup\$ With such argument the whole discussion is useless because on limited input the complexity is always O(1) ;-) \$\endgroup\$
    – Howard
    Aug 21, 2014 at 13:47
  • \$\begingroup\$ @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. \$\endgroup\$
    – Ray
    Aug 21, 2014 at 13:53
  • \$\begingroup\$ 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. \$\endgroup\$
    – Falko
    Aug 21, 2014 at 16:19
3
\$\begingroup\$

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

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.

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

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))))
\$\endgroup\$
3
  • \$\begingroup\$ can you add the print statement to make it testable ? It will not be counted in the score. \$\endgroup\$ Aug 22, 2014 at 8:15
  • 1
    \$\begingroup\$ Updated. I've run it on both your large examples, and got 58 and 57 as expected. \$\endgroup\$ Aug 22, 2014 at 15:25
  • \$\begingroup\$ I think you still need to call the function :p , but if you've tested it then that is enough . \$\endgroup\$ Aug 22, 2014 at 16:04
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ The algorithm you mentioned is the same as that used by @faubiguy. \$\endgroup\$
    – Ray
    Aug 21, 2014 at 18:17
  • \$\begingroup\$ @Ray you're right \$\endgroup\$ Aug 21, 2014 at 18:20
2
\$\begingroup\$

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)).                     ";
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – Howard
    Aug 21, 2014 at 13:07
  • \$\begingroup\$ please try the input in this link \$\endgroup\$ Aug 21, 2014 at 13:22
  • \$\begingroup\$ @Mostafa36a2 I did already (see comment before). After 5 seconds it returns 58. \$\endgroup\$
    – Howard
    Aug 21, 2014 at 13:24
  • \$\begingroup\$ this is another one , it should return 57 , so if your code did return 57 then it's Accepted :) Congratulations \$\endgroup\$ Aug 21, 2014 at 13:26
  • \$\begingroup\$ @Mostafa36a2 Ah, now I see those are two distinct test cases. Yes, your second link returns 57 as does my solution on this input. \$\endgroup\$
    – Howard
    Aug 21, 2014 at 13:44
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Yes , this is a timely manner :) \$\endgroup\$ Aug 21, 2014 at 15:15
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
11
  • 1
    \$\begingroup\$ you can change your parameter to int[] and then you'd have less characters because you wouldn't need to cast string to int \$\endgroup\$
    – Armin
    Aug 22, 2014 at 9:51
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Bob
    Aug 22, 2014 at 10:09
  • \$\begingroup\$ And c++;if(c>m)m=c; can be m=c++>m?m:c;, and you can again drop the braces around that. \$\endgroup\$
    – Bob
    Aug 22, 2014 at 10:15
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Bob
    Aug 22, 2014 at 10:21
  • 2
    \$\begingroup\$ 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;} \$\endgroup\$
    – Bob
    Aug 22, 2014 at 10:36
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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