Longest Increasing Subsequence

The longest increasing subsequence is the longest sequence that can be formed by taking elements in original order while values strictly increase.

The elements do not need to be contiguous.

Core Idea

A basic dynamic programming approach lets dp[i] mean the length of the longest increasing subsequence ending at index i. To compute it, the algorithm checks earlier indexes with smaller values.

This basic version has O(n^2) time complexity.

The phrase “ending at index i” is important. It makes the state specific enough to build from earlier states. If values[i] is the last value in the subsequence, the previous value must come from some earlier index j where values[j] < values[i].

Function Contract

lis_length(values) expects a list of comparable values.

It returns the length of the longest strictly increasing subsequence. The returned value is a length, not the subsequence itself.

Python Example

def lis_length(values):
    if not values:
        return 0
 
    dp = [1] * len(values)
 
    for i in range(len(values)):
        for j in range(i):
            if values[j] < values[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)

Each dp[i] stores the best subsequence length that ends at values[i].

Step-by-Step Meaning

For:

values = [10, 9, 2, 5, 3, 7]

when the algorithm reaches 7, it checks earlier smaller values such as 2, 5, and 3. If the best increasing subsequence ending at 5 has length 2, then appending 7 gives length 3.

The final answer is max(dp), not necessarily dp[-1], because the longest increasing subsequence may end before the last element.

Subsequence vs Subarray

A subsequence keeps order but may skip elements:

2, 5, 7

from [10, 9, 2, 5, 3, 7] is a subsequence.

A subarray must be contiguous. 2, 5, 7 is not a subarray in that input because 3 lies between 5 and 7.

Common Confusions

A subsequence is not the same as a subarray. A subsequence may skip elements. A subarray must be contiguous.

“Increasing” must match the problem statement. Strictly increasing uses <; non-decreasing uses <=.

Another common mistake is assuming sorting helps. Sorting would destroy the original order, and original order is part of the subsequence requirement.

When To Use It

Use longest-increasing-subsequence reasoning for ordered selection problems where elements must keep their original order while satisfying a comparison rule.

The O(n^2) DP is the version to understand first. A faster O(n log n) method exists, but it has a different invariant and is less direct as a first explanation.

The Main Point

The basic LIS DP works by asking what increasing subsequence ends at each index. The answer is the best over all ending positions.