How to make this Longest Increasing Subsequence program return this subsequence

Question

I have this code for Longest Increasing Subsequence. Right now it returns length of the longest increasing subsequence, but I don't know how to make it return this exact subsequence. For ex. in this case it should return [3,6,7,8,9]. Any ideas? I would appreciate not using very complicated syntax :D

a = [3, 6, 7, 2, 1, 8, 9, 5]
n = len(a)
q = [0] * n
for k in range(n):
    max = 0
    for j in range(k):
        if a[k] > a[j]:
            if q[j] > max:
                max = q[j]
    q[k] = max + 1
return(max(q))

outer loop iterates after all elements from a and inner loop checks if element k from table is greater than item from index 0 to k-1 Thanks to that q table for this example looks like this [1,2,3,1,1,4,5,2] We can see that first element makes subsequence of length 1, second one makes subsequence of length 2 (with first element), third element makes subsequence of length 3 (with first and second elements), fourth element makes subsequence of length 1 because non of previous elements is smaller than it, and so on. So basically at each iteration it gets the length of the longest increasing subsequence ending at index k

Shorter version of the same program:

for i in range(n):
        for j in range(i):
            if a[i] > a[j]:
                q[i] = max(q[i], 1 + q[j])

Abhishek Bansal Abhishek Bansal · Accepted Answer · 2020-05-12T16:33:12

It would have been great if you had described what your code was doing but as I understand at each iteration it gets the length of the longest increasing subsequence ending at index k.

To trace back the actual indices in the array, just add another array previous[].

Initialize previous = [-1] * n.

And then

if q[j] > max: 
   max = q[j]
   previous[k] = j

How to make this Longest Increasing Subsequence program return this subsequence

1 Answers