Longest Increasing Subsequence (LIS) Explained

Longest increasing subsequence (LIS) is a classic problem in computer science that’s usually solved using three main approaches: brute-force recursion with O(2ⁿ) complexity, dynamic programming with O(n²) complexity, and binary search with optimal O(n log n) complexity. The longest increasing subsequence problem teaches valuable techniques for handling sequence-based optimization and appears frequently in interviews and algorithm challenges.

In this tutorial, we’ll explore what LIS is, discuss its problem statement, walk through its different solutions, and more.

Let’s start the discussion with a brief overview of LIS.

What is longest increasing subsequence (LIS)?

The longest increasing subsequence (LIS) of a sequence is the longest possible subsequence where the elements are sorted in strictly increasing order. Importantly, this subsequence does not have to be consecutive — we can skip certain elements as long as the order of appearance is preserved.

To put it simply, if we have an array or sequence of numbers, the LIS represents the maximum-length subset of those numbers that are in ascending order. This problem helps us understand how to extract patterns of growth or improvement from a dataset.

Now that we’ve got an idea of what LIS is, let’s move on to defining its problem statement.

Problem statement for LIS

Given an array or sequence of integers, the task is to find the length of the longest subsequence where all elements are in strictly increasing order.

Let’s look at an example to visualize this:

Input: numbers = [0, 1, 0, 3, 2, 3] 
Output: 4 
Explanation: The LIS is [0, 1, 2, 3]. 

In this example, the subsequence [0, 1, 2, 3] is the longest sequence that satisfies the increasing order condition. Even though the elements are not consecutive in the original array, their order is maintained.

With the problem statement for longest increasing subsequence (LIS) clearly defined, we can now explore different ways to solve it — starting with the most intuitive, brute-force approach.

Brute-force solution for LIS

The brute-force solution for longest increasing subsequence (LIS) explores all possible subsequences in the array to find the longest one that is strictly increasing. The main idea is to make a binary choice for each element: include it in the current subsequence or skip it.

Approach

Here’s the brute-force approach for solving LIS:

Step 1: We define a recursive helper function that keeps track of two parameters:

• prev: The last element included in the current subsequence.
• curr_index: The index of the element currently being considered.

Step 2: At each element, we have two choices:

• Include the element in the subsequence, but only if it is greater than prev.
• Exclude the element and move to the next index.

Step 3: We recursively explore both choices for every element in the array.

After processing all elements, the maximum length between these two choices is the length of the LIS.

Implementation

Here’s the Python implementation of the brute-force approach for longest increasing subsequence using recursion:

def lis_bruteforce(nums): 
    def helper(prev, curr_index): 
        # Base case: End of the list 
        if curr_index == len(nums): 
            return 0 
         
        # Option 1: Skip current element 
        not_taken = helper(prev, curr_index + 1) 
         
        # Option 2: Take current element (if increasing) 
        taken = 0 
        if nums[curr_index] > prev: 
            taken = 1 + helper(nums[curr_index], curr_index + 1) 
         
        # Return the maximum between two choices 
        return max(taken, not_taken) 
     
    return helper(float('-inf'), 0) 
 
# Example 
numbers = [10, 9, 2, 5, 3, 7, 101, 18] 
print(lis_bruteforce(numbers)) 

Copy to clipboard
Copy to clipboard

In this example, the recursion starts with a previous value of −inf (−∞) so the first element can always be included.

The output will be:

4 

Copy to clipboard
Copy to clipboard

Time and space complexity

Time complexity: O(2ⁿ)

Each array element can either be included or excluded, resulting in 2ⁿ possible combinations. This makes it exponential and impractical for large input sizes.

Space complexity: O(n)

The recursion depth can go up to n, so we need O(n) stack space.

While the brute-force approach for LIS is easy to understand, it’s inefficient for large datasets. Let’s improve it using dynamic programming.

Dynamic programming solution for LIS

The dynamic programming approach leverages overlapping subproblems and avoids redundant calculations to solve the longest increasing subsequence (LIS) problem, making it suitable for larger sequences.

Approach

Here’s the dynamic programming approach for solving LIS:

Step 1: Initialize a dpg array of size n (length of the input array) with all values set to 1, because the minimum LIS ending at any element is 1 — the element itself.

Step 2: Iterate through the array using two nested loops:

• Outer loop: Current element nums[i]
• Inner loop: All previous elements nums[j] with j < i

Step 3: If nums[i] > nums[j], it means nums[i] can extend the increasing subsequence ending at nums[j]. We update dpg[i] as:

dpg[i] = max(dpg[i], dpg[j] + 1) 

Copy to clipboard
Copy to clipboard

After processing all elements, the maximum value in the dpg array is the length of the LIS.

Implementation

Here’s the Python implementation of the dynamic programming approach for longest increasing subsequence:

def lis_dpg(nums): 
    n = len(nums) 
    if n == 0: 
        return 0 
 
    # Initialize dpg array 
    dpg = [1] * n 
 
    # Build dpg array 
    for i in range(1, n): 
        for j in range(i): 
            if nums[i] > nums[j]: 
                dpg[i] = max(dpg[i], dpg[j] + 1) 
 
    # The maximum value in dpg is the LIS length 
    return max(dpg) 
 
# Example 
numbers = [10, 9, 2, 5, 3, 7, 101, 18] 
print(lis_dpg(numbers)) 

Copy to clipboard
Copy to clipboard

The output will be:

4 

Copy to clipboard
Copy to clipboard

Time and space complexity

Time complexity: O(n²)

The algorithm uses two nested loops over the array: for each element, we compare it with all previous elements.

Space complexity: O(n)

We store the LIS length for each element in the dp array, which requires linear space.

Dynamic programming is a big step forward, but we can make it even faster. Let’s use binary search to optimize the LIS calculation.

Binary search solution for LIS

The binary search approach for solving longest increasing subsequence (LIS) combines a greedy strategy with binary search to efficiently maintain the potential ends of increasing subsequences.

Approach

Here’s the binary search approach for solving LIS:

Step 1: Initialize an empty list sub to keep track of the smallest tail elements of increasing subsequences.

Step 2: Iterate through each element num in the input array:

• If num is greater than the last element in sub, append it to sub. This means we can extend the current increasing subsequence.
• Otherwise, use binary search to find the position in sub where num should be inserted (the first element greater than or equal to num) and replace that element. This ensures that sub always maintains the smallest possible tail values.

After processing all elements, the length of sub will give us the length of the LIS.

Implementation

Here’s the Python implementation of the binary search approach for longest increasing subsequence:

import bisect 

def lis_binary_search(nums): 
    sub = [] 

    for num in nums: 
        # Find the insertion position using binary search 
        i = bisect.bisect_left(sub, num) 

        # If num is greater than all elements, append it 
        if i == len(sub): 
            sub.append(num) 
        else: 
            # Replace the first element >= num 
            sub[i] = num 

    return len(sub) 

# Example 
numbers = [10, 9, 2, 5, 3, 7, 101, 18] 
print(lis_binary_search(numbers)) 

Copy to clipboard
Copy to clipboard

The output will be:

4 

Copy to clipboard
Copy to clipboard

Time and space complexity

Time complexity: O(n log n)

For each of the n elements, we perform a binary search on the sub list, which takes O(log n) time. Therefore, the total complexity is O(n log n).

Space complexity: O(n)

We maintain the sub list, which in the worst case can grow up to the size of the input array, requiring linear space.

Since we’re done discussing all the solutions, let’s explore some of the real-world applications of LIS.

Real-world applications of LIS

Longest increasing subsequence (LIS) has numerous real-world applications:

• Stock market analysis: To find the longest period of increasing stock prices.
• DNA sequencing: Comparing biological sequences to identify growth patterns.
• Data compression: Detecting structured order within sequences to improve encoding.
• Version control systems: Identifying minimal edit sequences between file versions.

As we can see, LIS already plays a crucial role across various domains and continues to be a fundamental tool in sequence analysis and optimization.

Conclusion

In this guide, we explored the longest increasing subsequence (LIS) problem in detail — from understanding its problem statement to solving it using three distinct approaches. Besides that, we also discovered some real-world applications of LIS.

LIS is more than just a classic algorithm problem—it’s a window into efficient sequence analysis. From basic approaches to optimized solutions, LIS teaches us how clever strategies can turn complex challenges into manageable tasks, making it a crucial tool for programmers and researchers alike.

If you want to learn more about dynamic programming in Python, check out the Pass the Technical Interview with Python course on Codecademy.

Frequently asked questions

1. What is longest increasing subsequence (LIS)?

The longest increasing subsequence (LIS) of a sequence is the longest subsequence in which every element is greater than the previous one, maintaining the original order of elements.

2. What is the time complexity of LIS?

The time complexity for solving longest increasing subsequence (LIS) depends on the method used:

• Brute-force: O(2ⁿ)
• Dynamic programming: O(n²)
• Binary search: O(n log n)

3. Which algorithm is most efficient for LIS?

The binary search algorithm proves to be the most efficient for solving longest increasing subsequence (LIS), achieving O(n log n) time complexity.

4. What are some real-world applications of LIS?

Longest increasing subsequence (LIS) is widely used in stock market trend analysis, DNA sequencing, data compression, and time-series analysis.

5. What are some related problems to LIS?

Some related problems to longest increasing subsequence (LIS) include:

• Longest Common Subsequence (LCS)
• Longest Bitonic Subsequence
• Maximum Sum Increasing Subsequence