Longest Increasing Subsequence.py

From Algorithmist
Jump to navigation Jump to search
#Finds a largest increasing subsequence in O(n^2) time
def LiS(array):
  n=len(array)
  #q[i] contains the max length of sub seq. ending at array[i]
  #p[i] contains predecessor of the sub seq. ending at array[i] 
  q=[0]*n
  p=[-1]*n
  
  for i in range(n):
    maxLen=0
    for j in range(i):
      if array[i]>array[j] :
        if q[j]>maxLen :
          maxLen=q[j]
          p[i]=j
    
    q[i]=maxLen+1
  
  idx=q.index(max(q))
  seq=[]
  while(idx!=-1):
    seq=[array[idx]]+seq
    idx=p[idx]
    
  return seq
  
def main():
  print LiS([4,2,6,1,9,0,11,7,12])
  
  
if __name__=='__main__':
  main()