5 Best Ways to Find the Length of the Longest Increasing Subsequence in Python

Rate this post

πŸ’‘ Problem Formulation: Finding the longest increasing subsequence (LIS) is a common algorithmic challenge which involves identifying the longest subsequence of a given sequence of numbers, where the subsequence’s elements are in sorted order, ascending, and strictly increasing. For instance, given the array [10, 9, 2, 5, 3, 7, 101, 18], the length of the LIS is 4, corresponding to the subsequence [2, 3, 7, 18].

Method 1: Dynamic Programming Approach

The dynamic programming approach to the longest increasing subsequence problem involves creating a table to store the lengths of the LIS ending with each element of the input array. This method offers a clear balance between readability and efficiency, with a time complexity of O(n^2).

Here’s an example:

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

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

Output: 4

The function length_of_lis() constructs an array dp where each element dp[i] holds the length of the LIS ending at the ith index. It iterates through each element, checking all previous elements to find an increasing sequence, which is then used to update the dp array. The length of the longest subsequence is the maximum value in dp.

Method 2: Patience Sorting (Binary Search)

Using patience sorting and binary search, this approach results in a more efficient solution to the LIS problem, with a reduced time complexity of O(n log n). It simulates a card game ‘Patience’ and involves placing each element of the given array into a ‘pile’, ensuring the top elements of piles are in increasing order.

Here’s an example:

from bisect import bisect_left

def length_of_lis(nums):
    end_elements = []
    for num in nums:
        i = bisect_left(end_elements, num)
        if i == len(end_elements):
            end_elements.append(num)
        else:
            end_elements[i] = num
    return len(end_elements)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

Output: 4

The length_of_lis() function uses binary search through bisect_left() from the bisect module to find the position at which the current element can be placed in the sorted sequence. It either extends the sequence or replaces the existing element to maintain the increasing order, and the length of the resulting sequence is the solution.

Method 3: Recursive Approach

The recursive method explores the LIS problem by breaking it down into smaller subproblems and solving each recursively. Although intuitive and straightforward in its implementation, this method is less efficient due to the exponential time complexity O(2^n), making it suitable only for small datasets.

Here’s an example:

def lis_util(nums, prev, curpos):
    if curpos == len(nums):
        return 0
    taken = 0
    if nums[curpos] > prev:
        taken = 1 + lis_util(nums, nums[curpos], curpos + 1)
    nottaken = lis_util(nums, prev, curpos + 1)
    return max(taken, nottaken)

def length_of_lis(nums):
    return lis_util(nums, float('-inf'), 0)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

Output: 4

The functions lis_util() and length_of_lis() work together to solve the problem recursively. lis_util() checks each element and decides whether to include it in the subsequence or not, comparing with previously included elements. The final answer is the maximum value obtained by including or excluding the current element.

Method 4: Memoization (Top-Down Dynamic Programming)

By employing the memoization technique, we can optimize the recursive solution by storing the results of subproblems and reusing them when necessary. This top-down dynamic programming approach improves the recursive method’s efficiency to a time complexity of O(n^2).

Here’s an example:

def lis_util(nums, prev_index, curpos, memo):
    if curpos == len(nums):
        return 0
    if memo[prev_index + 1][curpos] >= 0:
        return memo[prev_index + 1][curpos]
    
    taken = 0
    if prev_index  nums[prev_index]:
        taken = 1 + lis_util(nums, curpos, curpos + 1, memo)
    nottaken = lis_util(nums, prev_index, curpos + 1, memo)
    
    memo[prev_index + 1][curpos] = max(taken, nottaken)
    return memo[prev_index + 1][curpos]

def length_of_lis(nums):
    memo = [[-1 for _ in range(len(nums))] for _ in range(len(nums) + 1)]
    return lis_util(nums, -1, 0, memo)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

Output: 4

This example adds a memo parameter to the recursive function to store results that have already been calculated. The length_of_lis() function initializes this memoization table and then calls the recursive lis_util() function, which checks the table before computing new values, drastically reducing the number of computations.

Bonus One-Liner Method 5: Using functools and List Comprehensions

This single-line solution leverages the power of the functools module and Python’s list comprehensions to solve the LIS problem compactly. It’s an example of Python’s expressiveness but may sacrifice some readability.

Here’s an example:

from functools import reduce

def length_of_lis(nums):
    return len(reduce(lambda lst, x: lst[0:next((i for i, y in enumerate(lst) if y >= x), len(lst))] + [x], nums, []))

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))

Output: 4

In this one-liner, the reduce() function builds the increasing subsequence by iterating over the input list. For each number, it finds the position in the current list where it should be placed using a generator expression. Although concise, understanding this code requires familiarity with advanced Python features.

Summary/Discussion

  • Method 1: Dynamic Programming Approach. Easy to understand. Has O(n^2) time complexity, which is not efficient for large datasets.
  • Method 2: Patience Sorting (Binary Search). More efficient with O(n log n) time complexity. Good for larger datasets but more complex to understand.
  • Method 3: Recursive Approach. Intuitive but highly inefficient with O(2^n) time complexity. Not recommended for anything but small datasets.
  • Method 4: Memoization (Top-Down Dynamic Programming). Optimized recursion with a reasonable time complexity of O(n^2). Can handle medium-sized datasets well.
  • Method 5: One-Liner with functools. Extremely compact. Sacrifices the readability and efficiency of the other methods, but showcases Python’s linguistic capabilities.