Course contentsShow
← Computer Science
Lesson 926 of 2,87222. Dynamic ProgrammingFree lesson

Longest Increasing Subsequence (LIS)

Compute the length of the longest strictly increasing subsequence in an array with O(n²) DP.

Longest Increasing Subsequence (LIS)

What you'll learn: You'll learn how to compute the length of the longest strictly increasing subsequence in an array using O(n²) dynamic programming.

What is LIS?

Given an array of numbers, a subsequence is formed by deleting some (or no) elements without changing the order of remaining elements. An increasing subsequence is one where each element is strictly greater than the previous. The Longest Increasing Subsequence is the longest such subsequence you can find.

For example, in [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 101] with length 4.

The DP Approach

This problem exhibits both optimal substructure (the LIS ending at position i builds on solutions from earlier positions) and overlapping subproblems (we reuse computed lengths).

State definition: Let dp[i] = length of the longest increasing subsequence that ends at index i.

Transition: For each position i, look at all previous positions j where j < i. If array[j] < array[i], we can extend the LIS ending at j by including array[i]. So:

dp[i] = max(dp[j] + 1) for all j < i where array[j] < array[i]

Base case: Every single element forms an increasing subsequence of length 1, so dp[i] = 1 initially.

The answer is the maximum value in the entire dp array.

Complexity

We have two nested loops: the outer loop iterates through each position (n iterations), and for each position, the inner loop checks all previous positions (up to n comparisons). This gives us O(n²) time complexity and O(n) space for the dp array.

Key Takeaway: LIS uses bottom-up DP where each position's answer depends on all previous smaller elements, resulting in an O(n²) solution that checks every pair of positions.