Skip to content

Instantly share code, notes, and snippets.

@daeyun
Created September 15, 2013 00:16
Show Gist options
  • Save daeyun/6566900 to your computer and use it in GitHub Desktop.
Save daeyun/6566900 to your computer and use it in GitHub Desktop.
length of longest increasing subsequence
#!/usr/bin/python
def lisBigger(prev, A):
if len(A) == 0:
return 0
max = lisBigger(prev, A[1:])
if A[0] > prev:
L = 1 + lisBigger(A[0], A[1:])
if L > max:
max = L
return max
X = [0, 3, 2]
# returns 2 because subsequence [0, 2] is increasing
print lisBigger(-999, X)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment