educative.io

Educative

Longest Increasing Subsequence path construction

Hi,
The code we currently have for Longest Increasing Subsequence in the “Grokking Dynamic Programming” is only for the count.

How can we modify it to give us all the numbers that will be included in the Longest Increasing Subsequence?

Thank you

I think you might have to resort to an iterative approach for this.
You can use nested for loops to traverse the list and store the sequences. Then, you can compare their lengths and select the longest one.

Perhaps this would work:

def longestincreasingsequence(arr):

if len(arr)==0:
    return []

LIS = [[] for _ in range(len(arr))]
LIS[0].append(arr[0])
for i in range(1, len(arr)):
    for j in range(i):
        # find the longest increasing subsequence that ends with `arr[j]`  where `arr[j]` is less than the current element `arr[i]`
        if arr[j] < arr[i] and len(LIS[j]) > len(LIS[i]):
            LIS[i] = LIS[j].copy()
    LIS[i].append(arr[i])

# `j` will store the index of LIS
j = 0
for i in range(len(arr)):
    if len(LIS[j]) < len(LIS[i]):
        j = i

print(LIS[j])