Questions: Longest Increasing Subsequence (LIS) Problem

Question 1

While running the O(n log n) LIS algorithm on [3, 1, 4, 1, 5, 9, 2, 6], after processing all elements the tails array is [1, 2, 5, 6]. Which statement is correct?

• A. The longest increasing subsequence is 1, 2, 5, 6 taken directly from the input
• B. The length of the LIS is 4, but the actual subsequence must be reconstructed separately
• C. The tails array length is wrong — the LIS length should be 5 since 9 appeared
• D. The algorithm failed because replacing 4 with 2 corrupted the subsequence

Answer: (B)

The tails array is a bookkeeping structure, not the actual LIS. Its length (4) is correct — the LIS length is 4 — but [1, 2, 5, 6] does not correspond to any single valid increasing subsequence: 2 appears at index 6 in the input while 5 appears at index 4, so 1→2→5→6 cannot be read left-to-right from the array. The actual LIS (such as [1, 4, 5, 9] or [1, 4, 5, 6]) must be reconstructed by tracking parent pointers during the algorithm. Option D misunderstands the algorithm: replacing 4 with 2 is correct because a subsequence of length 2 ending in 2 is more extensible than one ending in 4.

Question 2

In the O(n log n) LIS algorithm, why must the tails array always remain sorted?

• A. So that duplicate elements can be detected and skipped
• B. Because the DP recurrence requires tails in ascending order to compute dp[i]
• C. So that binary search can locate the correct insertion position in O(log n)
• D. So that the actual LIS can be read off directly from left to right

Answer: (C)

The entire O(n log n) speedup comes from replacing the O(n) inner scan of the O(n²) DP with a binary search. Binary search requires a sorted array. The tails invariant — tails[k] stores the smallest possible tail of any increasing subsequence of length k+1 — guarantees sorted order: a length-2 subsequence must end at a smaller value than any length-3 subsequence's tail. If the array weren't sorted, binary search would be invalid and you'd be back to linear scanning, losing the speedup.

Question 3

The tails array in the O(n log n) LIS algorithm directly stores the actual longest increasing subsequence found in the input.

• T. True
• F. False

Answer: False

This is the central misconception about the algorithm. The tails array is a bookkeeping structure that tracks the smallest possible tail element for subsequences of each length. When an element replaces an existing tail, the resulting array may not correspond to any valid subsequence of the input — the indices don't have to appear in increasing order. The tails array length equals the LIS length, which is the answer the algorithm reports, but the actual subsequence requires separate reconstruction using parent pointers.

Question 4

For any input sequence of length n, the O(n log n) LIS algorithm performs exactly n binary searches on the tails array.

• T. True
• F. False

Answer: True

Every element of the input is processed exactly once: for each element, one binary search on the tails array finds its insertion position, then the element either appends (extending the longest subsequence) or replaces an existing tail entry. This gives exactly n binary searches, each costing O(log n) — yielding the O(n log n) total runtime. No element is revisited or skipped.

Question 5

Why does the O(n log n) LIS algorithm replace an existing tail entry rather than simply skipping elements that don't extend the current longest subsequence? What invariant does replacement maintain?

Model answer: Replacement keeps future options open by minimizing each tail value. The invariant is that tails[k] holds the smallest possible tail for any increasing subsequence of length k+1 seen so far. A new element that is smaller than tails[k] but larger than tails[k-1] can start a length-(k+1) subsequence ending lower, making future extensions easier. Skipping it would preserve a larger tail value, incorrectly blocking valid extensions and potentially returning a wrong (too-short) LIS length.

The tails invariant is what keeps the array sorted and enables binary search. Minimizing each tail maximizes the chance that future elements can extend a subsequence of that length. This is the key insight separating the O(n log n) approach from naive DP: instead of tracking every possible ending value, you track only the best (smallest) ending value at each length. The binary search then asks: 'what is the longest subsequence this new element can extend?' — which is equivalent to finding the rightmost tail smaller than the new element.