The tails array maintains the smallest ending element for each LIS length. = smallest last element of any LIS of length . Key invariant: is always sorted. Why? A longer LIS must end with a larger element than a shorter one ending at an earlier position.
When we see a new element : if , we can extend. Otherwise, find the first and replace it. Replacing keeps optimal: we now have a smaller ending element for that length, enabling more extensions later.