#
# 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