Posted By

rishi_devan on 08/11/15


Tagged


Versions (?)

Longest Increasing Subsequence


 / Published in: Python
 

Dynamic Programming

  1. def lis(arr):
  2. n = len(arr)
  3. m = [0]*n
  4. for x in range(n-2,-1,-1):
  5. for y in range(n-1,x,-1):
  6. if arr[x] < arr[y] and m[x] <= m[y]:
  7. m[x] += 1
  8. max_value = max(m)
  9. result = []
  10. for i in range(n):
  11. if m[i] == max_value:
  12. result.append(arr[i])
  13. max_value -= 1
  14. return result
  15.  
  16. arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
  17. print(lis(arr))

Report this snippet  

You need to login to post a comment.