# # Longest Increasing Subsequence (LIS) # # Given a sequence A of numbers, return the maximal length of any # subsequence of A consisting of strictly increasing numbers. # # We develop a dynamic-programming solution: we model the problem as a # choice between a series of sub-problem defined as follows: let # DP(A,i) denote the maximal length of any sub-sequence ending at # position i. Then, DP(A,i) = min { DP(A,j) + 1 } over all positions # j < i such that A[j] < A[i] (since A[i] *extends* the sequence # ending at position j). With DP(A,i), we can compute the maximal # overall: LIS(A) = min { DP(A,i) } for all i = 0,...,n-1 # def LIS (A): # return the length of the longest increasing subsequence in A l = 1 for i in range(len(A)): l = max(l, DP(A,i)) return l def DP (A,i): # return the length of the longest increasing subsequence in A # that ends at position i l = 1 for j in range(i): if A[j] < A[i]: l = max(l, DP(A,j) + 1) return l # # The above solution is a straightforward, recursive implementation of # the dynamic-programming solution. However, this solution is # inefficient. One way to make it efficient is to develop it in a # simple sequence. Below is the same dynamic-programming solution # written as an iterative algorithm. # def LIS_itr (A): n = len(A) assert n > 0 DP = [1]*n best = 1 # best length seen so far for i in range(1,n): for j in range(i): if A[j] < A[i]: DP[i] = max(DP[i], DP[j] + 1) best = max(best, DP[i]) return best # # The solutions seen so far compute the maximal *length* but do not # output a maximal subsequence. We can easily modify the iterative # solution above to do just that. # def LIS_itr_seq (A): n = len(A) assert n > 0 DP = [1]*n P = [None]*n # "previous" elements in the maximal # sequence ending at position i best_i = 0 # for i in range(1,n): for j in range(i): if A[j] < A[i] and DP[j] + 1 > DP[i]: DP[i] = DP[j] + 1 P[i] = j if DP[i] > DP[best_i]: best_i = i S = [] # S will contain the maximal sequence i = best_i while i != None: # We build the maximal sequence S.append(A[i]) # backwards, following the "previous" i = P[i] # chain, starting from best_i i = 0 j = len(S) - 1 while i < j: # Then we simply reverse S S[i], S[j] = S[j], S[i] i = i + 1 j = j - 1 return S