Revision: 69660
Updated Code
at August 12, 2015 15:22 by rishi_devan
Updated Code
def lis(arr): n = len(arr) m = [0]*n for x in range(n-2,-1,-1): for y in range(n-1,x,-1): if arr[x] < arr[y] and m[x] <= m[y]: m[x] += 1 max_value = max(m) result = [] for i in range(n): if m[i] == max_value: result.append(arr[i]) max_value -= 1 return result arr = [10, 22, 9, 33, 21, 50, 41, 60, 80] print(lis(arr))
Revision: 69659
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at August 11, 2015 19:00 by rishi_devan
Initial Code
def LIS(A): m = [0]*len(A) for x in range(len(A)-2,-1,-1): for y in range(len(A)-1,x,-1 ): if A[x] < A[y] and m[x] <= m[y]: m[x] += 1 max_value = max( m ) result = [] for i in range( len( m ) ): if max_value == m[i]: result.append(A[i]) max_value -= 1 return result arr = [8,1,2,3,0,5] print(LIS(arr))
Initial URL
Initial Description
Dynamic Programming
Initial Title
Longest Increasing Subsequence
Initial Tags
Initial Language
Python