) Write a dynamic programming algorithm to solve the longest increasing subseque
ID: 3676888 • Letter: #
Question
) Write a dynamic programming algorithm to solve the longest increasing subsequence (LIS) problem. You are given an array a of n integers. An increasing subsequence is a sequence k indices
0 i1 < i2 < · · · < ik (n 1)
such that a[i1] < a[i2] < · · · < a[ik]
Given a find the longest increasing subsequence. I.e, an increasing subsequence i1, . . . , ik whose length k is the longest possible.
Example: Input is a : [1, 5, 2, 3, 8]. The longest increasing subsequence has length 4. i1 = 0, i2 = 2, i3 = 3, i4 = 4 yielding the elements 1, 2, 3, 8. Let us define the function lis(a, j, M) as the length of the LIS for the first j elements of the array (a[0] · · · a[j 1]), where j ranges from 0 to n and all elements of this subsequence are less than M.
(A) For the array a : [1, 5, 2, 3, 8] write down the values of lis(a, 3, 2) and lis(a, 5, ).
(B) Write down the base cases for lis(a, 0, M).
(C) Write down a recurrence for lis(a, j, M) for any j with 1 j n.
(D) Describe a bottom-up scheme to memoize the recurrence lis above. Describe the memo table itself: how many rows? how many columns? what do the rows and columns stand for? How are the base cases filled out in the table? How is each entry of the memo table filled out? Also, show how the filled out memo table for the example array a : [1, 5, 2, 3, 8].
(E, Extra Credit) Program your dynamic programming scheme in Python. Input to your function is the list a and output should be the LIS itself.
Explanation / Answer
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
Recursive Solution of LIS:
""" To make use of recursive calls, this function must return
two things:
1) Length of LIS ending with element arr[n-1]. We use
max_ending_here for this purpose
2) Overall maximum as the LIS may end with an element
before arr[n-1] max_ref is used this purpose.
The value of LIS of full array of size n is stored in
*max_ref which is our final result """
# global variable to store the maximum
global maximum
def _lis(arr , n ):
# to allow the access of global variable
global maximum
# Base Case
if n == 1 :
return 1
# maxEndingHere is the length of LIS ending with arr[n-1]
maxEndingHere = 1
"""Recursively get all LIS ending with arr[0], arr[1]..arr[n-2]
IF arr[n-1] is maller than arr[n-1], and max ending with
arr[n-1] needs to be updated, then update it"""
for i in xrange(1, n):
res = _lis(arr , i)
if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:
maxEndingHere = res +1
# Compare maxEndingHere with overall maximum.And update
# the overall maximum if needed
maximum = max(maximum , maxEndingHere)
return maxEndingHere
def lis(arr):
# to allow the access of global variable
global maximum
# lenght of arr
n = len(arr)
# maximum variable holds the result
maximum = 1
# The function _lis() stores its result in maximum
_lis(arr , n)
return maximum
########Dynamic Programing################
# Dynamic programming Python implementation of LIS problem
# lis returns length of the longest increasing subsequence
# in arr of size n
def lis(arr):
n = len(arr)
# Declare the list (array) for LIS and initialize LIS
# values for all indexes
lis = [1]*n
# Compute optimized LIS values in bottom up manner
for i in range (1 , n):
for j in range(0 , i):
if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
lis[i] = lis[j]+1
# Initialize maximum to 0 to get the maximum of all
# LIS
maximum = 0
# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum , lis[i])
return maximum
# end of lis function
# Driver program to test above function
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print "Length of LIS is", lis(arr)
# Dynamic programming Python implementation of LIS problem
# lis returns length of the longest increasing subsequence
# in arr of size n
def lis(arr):
n = len(arr)
# Declare the list (array) for LIS and initialize LIS
# values for all indexes
lis = [1]*n
# Compute optimized LIS values in bottom up manner
for i in range (1 , n):
for j in range(0 , i):
if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
lis[i] = lis[j]+1
# Initialize maximum to 0 to get the maximum of all
# LIS
maximum = 0
# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum , lis[i])
return maximum
# end of lis function
# Driver program to test above function
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print "Length of LIS is", lis(arr)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.