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 [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 &lt;= 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


Dennis CJam - 22
isaacg Pyth - 26
Howard GolfScript - 35
proud haskeller Haskell - 56
Ray Python 3 - 66
histocrat Ruby - 67
DLeh C# - 92
YosemiteMark Clojure - 94
faubiguy Python 3 - 113
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())))