Q:

How does finding a Longest Increasing Subsequence that ends with a particular element leads to the solution of finding LIS

I have understood that to find the solution of LIS problem, we need to find a LIS for every subsequence starting from initial element of the array to the each element that ends with a particular element(the last element), but I am not able to understand how would that help in finally finding a LIS of a given unsorted array, I also understand that this leads to an optimal substructure property and then can be solved, but as mentioned, I dont see how finding LIS(j) that ends with arr[j] will help us.
thanks.

A:

Consider this sequence as an example:
a[]   : 10 20  1  2  5 30  6  8 50  5  7

It produces the following sequence of LIS[i]:
a[]   : 10 20  1  2  5 30  6  8 50  5  7
LIS[] :  1  2  1  2  3  4  4  5  6  3  4

Given this sequence, you can immediately find the length of the result, and its last element: the length is 6, and the last element is 50.
Now you can unfold the rest of the sequence, starting from the back: looking for LIS of 5 (one less than that of element 50) such that the number is less than 50 yields 8. Looking back further for 4 gives you 6 (there is no tie, because 30 is above 8). Next comes 5 with LIS of 3, and then a 2 with LIS of 2. Note that there is no tie again, even though 20 has the same LIS. This is because 20 is above 5. Finally, we find 1 with LIS of 1, completing the sequence:
50  8  6  5  2  1

Reversing this produces the longest increasing subsequence:
1 2 5 6 8 50

This is a common trick: given a table with the value of the function that you are maximizing (i.e. the length) you can produce the answer that yields this function (i.e. the sequence itself) by back-tracking the steps of the algorithm to the initial element.

