[MUSIC] Previously we designed an algorithm for finding the lengths of an optimal increasing subsequence. Now we're going to show how to find the longest increasing subsequence itself. For this we are going to store an additional array, showing for which i not only the lengths of an optimal increase in subsequence ending of this particular element pi but also the previous element in this subsequence. Here is our previous code with three small additions. First of all, we allocate in the array prev in the very beginning, then in the loop we first initialize prev [i] = -1. This basically means that at this point we don't have any previous element in our currently longest increasing subsequence ending at the element i. Recall that at this point the only increasing subsequence that we know that ends at the element i consists of just a single element i. So there is no previous element so prev[1] = -1. Then, when computing the solution for the top problem ending at an element i, each time when we find a better solution through the previous element j, we actually change prev[i] to j. This basically means that at this point, the longest increasing subsequence ending at an element i, has j as the second to last element. Okay, so let's give an example. Using this example we are also going to show how to uncover a solution. So what you see here is the result of applying this algorithm to our sample array, okay? So we see that the length of an optimal increasing subsequence is equal to 5, just because 5 is the maximum value in our table T. In particular since T of 13 is equal to 5, this means that there is a longest increase in subsequence ending at the element 5. Okay, so we're going to unwind our optimal increase in subsequence from right to left. So we already now its element. This element is number 13. So prev of 13 is equal to 9. This basically means that 9 is the second to last element in this subsequence. So let's go to element 9. At this point we have already recovered the last two element of an optimal increasing subsequence, namely the last element is element 13, the previous element is element number 9. To find out the element that goes before the element 9, we simply look at prev of 9. It is equal to 5. Meaning that the previous element is 5. Then to find out the element that goes before the fifth element, we look at prev of 5, and so on. So this way we will uncover the whole optimal increase in subsequence. We stop this process when we find that prev of our current element is equal to -1. This basically means that there is no previous element for this particular element. Now let's implement it. So for this we first need to find the largest element in our table T. This can be done just by scanning the array T from left to right. Okay, then what we're going to do is to uncover our optimal solution. For this, we are going to use the list lis. So we start with the element k, where the value of the table T, is maximal. Then what we are going to do in a loop is the following. We put k to lis, and then we replace k with prev of k. And we repeat this process until prev of k is equal to -1. This means that there is no previous element. And each time we append the current element k to our longest increasing subsequence, to the variable lis. So recall that, in this case, we actually unwind our longest increasing subsequence from right to left. So in the end, we need to reverse this sequence and then to print or to return the result. Now let me also mention the following interesting fact. So in fact we do not need the array prev in order to reconstruct the optimal increasing subsequence. So recall that the fact that the maximum value in T is equal to 5. Means that the longest increase in subsequence in our sample array has lengths 5. So let's just stand at some position where T is equal to 5. So what we know is that this is the last element of some longest increase in subsequence of lengths 5. But what this means is that the prefix of this longest increase in subsequence, its length is equal to 4. And this in turn means that to find the previous element it is enough to scan the table T from right to left and to find the position where we have 4 in the table T, such that the corresponding element of the initial array A is smaller than the last element of our longest increasing subsequence. So essentially this means that what we need to do is to find a pattern like 5, 4, 3, 2, 1 in our table T, such that the correspondent elements of our initial array are decreasing. So they are decreasing because we go from right to left. And this can be done just with a simple scan from right to left, starting with the last element of the longest increasing subsequence. Let's now summarize. By analyzing the structure of an optimal solution for the longest increasing subsequence problem we realized that it makes sense to compute the following values. To define the following set problems. For every element i from 0 to n-1 we defined lis of i as the lengths of the longest increasing subsequence ending at an element i. Using the subprograms we can define the recurrence relation that allows to express the value for lis of i, through the values of lis of j, for J small as an i. Then when we wrote down this recurrence relation we converted it into recursive algorithms, just by adding minimization, just by adding a table where we stored all the intermediate results. Our next step was to convert this recursive algorithm into an iterative algorithm. So we just filled in the table T from left to right, one by one. Okay, and finally, we were able to reconstruct our solution using some additional bookkeeping information such that for every subproblem we stored not only it's solution, not only the length of an optimal solution ending at this particular element, but also the choice leading to these optimal solutions. So in this case, this was the previous element in the longest increase in subsequence ending at the i-th element.
