Purpose of the Array

Once we understand the purpose of the array LISArray, the algorithm itself is pretty easy to understand. In the examples below, LISArray's indices are a result from scanning the entire input arr. Note that at index j, it is storing the result of the smallest element in the entire array that occurs at the end of a subsequence of length j.

This is interesting because note the following;

1LISArray: {3, 4, 8}
2arr[LISArray[i]] = 1, 6, 8     // (for i=1..2)

So the important point to note is that LISArray stores the indices of the items of input array in sorted order!

Hence the following is true:

1    arr[LISArray[1]] < arr[LISArray[2]] < arr[LISArray[3]] < arr[LISArray[4]] ...
2    arr[LISArray[j]] < arr[LISArray[j+1]]