Advanced Search

Longest Increasing Subsequence

/ Published in: Python
Save to your folder(s)
Dynamic Programming

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.