Find Longest Increasing Subsequence Length in Python

Compute the length of the longest increasing subsequence in an array using dynamic programming.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 16 views 0 copies

dynamic-programming subsequence algorithm lis

Python code

18 lines

Python 3.9+

def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

if __name__ == "__main__":
    # Demo with a sample sequence
    sequence = [10, 9, 2, 5, 3, 7, 101, 18]
    print(f"Sequence: {sequence}")
    print(f"Longest increasing subsequence length: {longest_increasing_subsequence(sequence)}")

Output

stdout

Sequence: [10, 9, 2, 5, 3, 7, 101, 18]
Longest increasing subsequence length: 4

How it works

This solution uses dynamic programming to avoid brute-force enumeration. dp[i] stores the length of the longest increasing subsequence that ends at index i. The algorithm iterates through every position and checks all earlier elements; if an earlier element is smaller, it extends that subsequence by one. The result is the maximum value in dp, which represents the overall longest increasing subsequence length.

Common mistakes

Forgetting to handle an empty list, causing a ValueError on `max(dp)`.
Confusing the length with the actual subsequence; this only returns the length.
Using `>=` instead of `>` which breaks strictly increasing condition.

Variations

Use a binary search approach with a patience-sorting array to achieve O(n log n) time.
Return the actual subsequence by tracking indices instead of just the length.

Real-world use cases

Analyzing stock price trends to find the longest period of continuous growth.
Determining the maximum number of compatible tasks in scheduling problems.
Measuring the degree of sorting in a dataset for data quality checks.

Find Longest Increasing Subsequence Length in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes