An Efficient Algorithm for Running LIS

LIS using dynamic programming still requires O(n^2) computations. Can you find an improved algorithm that uses O(n log n) time?

To understand how the solution of finding LIS can be made more efficient, let's review binary search first. We can improve upon the computation time by making use of the fact that it takes O(log n) time to search for an item in a sorted array when using binary search.

Coming back to finding LIS-- we'll use an intermediate array again called LISArray. Let us define its purpose in this instance, and highlight a few important points:

1. We will use LISArray to store indices of the input array arr.

2. We'll also use LISArray to keep track of the longest subsequence found so far.

3. LISArray[j]: LISArray[j] will map to the index of the smallest item of arr that's the last item for a subsequence of length j.

4. arr[LISArray[j]]: Ending element of subsequence of length j.

5. Size of LISArray[j] = (Size of arr)+ 1, as LISArr[j] has information on subsequence of length j, indices start at zero so we need an additional element to store the maximum possible length.

6. LISArray[0] is unused.

7. Maximum index of LISArray can be at (Size of arr).