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.

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].

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 <=.

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.