Oh My Algorithm
Algorithm Guidecomplexity: O(n²)

Longest Increasing Subsequence (LIS)

Finds the length of the longest increasing subsequence you can pick while preserving order. dp[i] is defined as the subsolution 'length of the LIS ending at element i', and reusing the subsolutions of earlier, smaller elements pulls the O(2ⁿ) brute force down to O(n²).

01Longest Increasing Subsequence (LIS)

Finding the longest increasing subsequence. Fill in, from left to right, the length of the longest increasing run ending at each value.

Every cell starts at 1. Any value on its own already forms an increasing run of length 1.

Among the smaller values before 22, the longest run ends at 10. Extending it makes the length 2.

Nothing smaller comes before 9. With nothing to extend, the length stays at 1.

Among the smaller values before 33, the longest run ends at 22. Extending it makes the length 3.

Among the smaller values before 21, the longest run ends at 10. Extending it makes the length 2.

Among the smaller values before 50, the longest run ends at 33. Extending it makes the length 4.

Among the smaller values before 41, the longest run ends at 33. Extending it makes the length 4.

Among the smaller values before 60, the longest run ends at 50. Extending it makes the length 5.

The longest increasing subsequence is 10 → 22 → 33 → 50 → 60 — length 5. The largest value in the table is the answer.

10·
22·
9·
33·
21·
50·
41·
60·
1 / 10

02 Understand It Simply

For Everyone
🔑How It Works

For each position it computes the length of the longest increasing subsequence ending there, building on the results already computed to its left.

💡In Plain Words

Fills a table with the length of the longest increasing subsequence ending at each position.

Reusing earlier results makes it efficient.

📍Where It's Used
  • –Trend analysis
  • –version-compatibility checks
  • –sequence problems

03 Python Implementation

A clean, readable reference implementation of the core logic of Longest Increasing Subsequence (LIS).

core_implementation.py
def lis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

04 Frequently Asked Questions

FAQ
What is Longest Increasing Subsequence (LIS)?+

Finds the length of the longest increasing subsequence you can pick while preserving order. dp[i] is defined as the subsolution 'length of the LIS ending at element i', and reusing the subsolutions of earlier, smaller elements pulls the O(2ⁿ) brute force down to O(n²).

What is the time complexity of Longest Increasing Subsequence (LIS)?+

The time complexity of Longest Increasing Subsequence (LIS) is O(n²). Follow the step-by-step visualization to see exactly why.

Where is Longest Increasing Subsequence (LIS) used?+

Trend analysis, version-compatibility checks, sequence problems.

What's a simple analogy for Longest Increasing Subsequence (LIS)?+

For each position it computes the length of the longest increasing subsequence ending there, building on the results already computed to its left.

→ Dynamic Programming — see allRelated
🧠Fibonacci Sequence (DP)
O(n)