optimization pseudocode question

Question 88 points
In class we saw a dynamic programming solution which takes as input an array of heights H[1……….n]
and returns the length of the longest increasing subsequence of heights. The pseudo-code from class is
copied below.
Longest IncreasingSubsequence (H[])
Step 1: Initialize the table: L [1] = 1
Step 2: Fill in the table from left to right:
for k = 2 to n
max = 1
for i
1 to k 1
–
Your job is to:
if H[i] < H[k] if L[i] +1 > max
L[k] = max
max = L[i] +1
Return maximum of L[1], L[2],…, L[n]
• Update the pseudo-code above so that the algorithm also keeps track of longest increasing subse-
quence.
• Write the pseudo-code that outputs the longest increasing sequence of heights. Your algorithm
must run in O(n) time.