Longest Increasing Subsequence

Learning goal: Identify what must be optimized when selecting an increasing subsequence.

Core idea A subsequence keeps the original left-to-right order, but it may skip elements. We want the largest number of selected values such that every next value is strictly greater than the previous one. The answer is a length, not the subsequence itself.

Algorithm plan

• Scan the array from left to right.
• Decide whether each number can extend an increasing sequence.
• Preserve enough information about earlier choices to make the best future decisions.
• Return the maximum achievable length.

Micro-example For [10,9,2,5,3,7,101,18], the values [2,3,7,101] form an increasing subsequence. The answer is therefore 4, even though the selected values are not contiguous.

Pitfalls

• A subsequence is not required to occupy consecutive positions.
• Increasing means strictly increasing, so equal values cannot extend a sequence.
• The goal is length; returning the actual values requires extra reconstruction logic.

Recap

• Preserve order while allowing skips.
• Maximize the number of selected values.
• The sample answer is 4.

Learning goal: Understand why keeping the smallest possible tail makes longer subsequences easier to build.

Core idea For every achievable length, keep the smallest ending value seen so far. A smaller tail is more flexible: it leaves more room for a future number to extend the sequence. We do not need to remember every sequence, only the best tail for each length.

Data structure model

• tails[k] is the smallest tail of any increasing subsequence of length k + 1.
• tails is always sorted in strictly increasing order.
• For each incoming number, binary search for the first tail greater than or equal to it.
• Replace that tail, or append if the number is larger than every tail.

Micro-example After processing 2,5,3, the tails array is [2,3]. The length-two sequence ending at 3 is more promising than one ending at 5.

Pitfalls

• tails stores optimal tail values, not necessarily values from one real subsequence.
• Use the first index with tails[index] >= x; this is lower bound.
• Equal values replace a tail rather than increasing the answer.

Recap

• Smaller tails create more extension opportunities.
• Binary search finds the correct tail to replace.
• The length of tails is the answer.

Learning goal: Connect the direct dynamic programming solution to the binary-search optimization.

Core idea The O(n²) method defines dp[i] as the longest increasing subsequence ending exactly at index i. For every earlier index j, we can extend dp[j] when nums[j] < nums[i]. This is clear but compares many pairs.

Recurrence

dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i].

The optimized method groups states by subsequence length instead of by ending index. Because tails is sorted, lower-bound binary search replaces a linear scan.

Algorithm plan

• Start with an empty tails array.
• For each x, find the first position k where tails[k] >= x.
• Replace tails[k] with x; if no such position exists, append x.
• Return len(tails).

Micro-example Reading 2,5,3 produces [2], then [2,5], then [2,3]. The length stays 2, but the tail becomes easier to extend.

Pitfalls

• The optimized method does not calculate every dp[i] value.
• Binary search must use lower bound for a strictly increasing subsequence.
• Replacing a tail preserves the best length so far; it does not reduce the answer.

Recap

• DP is indexed by ending position.
• tails is indexed by subsequence length.
• Sorted tails enable O(log n) updates.

Learning goal: Trace lower-bound insertion on one complete input and see how tails evolves.

Core idea Each number asks one question: where is the first tail that is at least this number? Replacing there keeps the same subsequence length alive with a better ending value. Appending means the number extends every known length and creates a new record.

Algorithm plan

• Process [10,9,2,5,3,7,101,18] from left to right.
• Binary search the current sorted tails array.
• Replace the first value greater than or equal to the incoming number.
• Read the final array length as the result.

Micro-example After processing 2,5,3,7, the state is tails = [2,3,7]. When 101 arrives, it is larger than all tails, so it appends and creates length 4. When 18 arrives, it replaces 101; the length remains 4.

Pitfalls

• Replacing 101 with 18 does not erase the known length-four possibility.
• A replacement is not an extension unless it occurs beyond the current last index.
• The binary-search range is always the current tails, not the original input.

Recap

• Process each value once.
• Search and update a sorted tail summary.
• Final tails length is 4 for this example.

Learning goal: Avoid the implementation mistakes that invalidate the tails method.

Core idea The algorithm is compact because its invariant carries a lot of meaning. The most important distinction is that tails is a summary of best possible endings by length, not a record of one chosen path through the input. Its length is correct even when adjacent entries came from incompatible positions.

Algorithm plan

• Use lower bound: find the first tails[k] >= x.
• Replace that slot, or append when x exceeds every tail.
• Keep the array sorted after every operation.
• Treat duplicates as replacements, not extensions.

Micro-example For input [2,5,3], the final tails is [2,3]. This happens to be a valid subsequence here, but that coincidence is not required by the invariant.

Pitfalls

• Using upper bound (> x) would allow equal values to extend the sequence.
• Returning the last tail value instead of tails.length answers the wrong question.
• Forgetting to process values in input order changes the problem.

Recap

• Lower bound enforces strict increase.
• tails is not necessarily a real subsequence.
• Only its length represents the answer.

Learning goal: Explain why the optimized solution meets the target bounds and recognize when to use it.

Core idea There are n input values. Each value performs one binary search over the sorted tails array, taking O(log n) time, followed by a replacement or append. The array uses O(n) space in the worst case, such as when the input is already increasing.

Algorithm plan

• Maintain tails as a sorted list.
• For each x, binary search its lower-bound position.
• Replace the first tail at least x, or append x.
• Return tails.length.

Micro-example For [10,9,2,5,3,7,101,18], the final state is [2,3,7,18]. The algorithm performs eight searches and returns 4.

Pitfalls

• The O(n²) DP is useful for learning and may be acceptable for smaller inputs, but it misses the target O(n log n) performance.
• Binary search is valid only because tails remains sorted.
• The optimized array gives the length directly; reconstructing the sequence needs predecessor metadata.

Recap

• Time: O(n log n).
• Space: O(n).
• Smallest tails preserve the correct LIS length without storing every subsequence.