Longest increasing subsequence in Python

The longest increasing subsequence (LIS) problem is a classic computer science problem that involves finding the longest subsequence of a list such that the subsequence elements are in increasing order. This subsequence is not required to be contiguous. Understanding how to find the LIS efficiently is essential for various applications, including data analysis, algorithm design, and optimization problems. This article will explore multiple methods to find the longest increasing subsequence in Python, complete with detailed explanations and code examples. We’ll cover dynamic programming and other optimization techniques to tackle this problem effectively.

Let’s start with an example:

 Input: [3, 10, 2, 1, 20]
 Output: [3, 10, 20] or [2, 10, 20] or [1, 10, 20]  (Length: 3)
 

Method 1: Dynamic Programming Approach

Dynamic programming provides an efficient way to solve the longest increasing subsequence problem. We build an array to store the lengths of the longest increasing subsequences ending at each index.

 def longest_increasing_subsequence_dp(nums):
     """
     Finds the longest increasing subsequence using dynamic programming.

     Args:
         nums (list): A list of numbers.

     Returns:
         list: The longest increasing subsequence.
     """
     if not nums:
         return []

     n = len(nums)
     dp = [1] * n  # Initialize dp array with 1 (each element is a subsequence of length 1)
     predecessors = [None] * n # Store predecessors to reconstruct the LIS

     for i in range(1, n):
         for j in range(i):
             if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                 dp[i] = dp[j] + 1
                 predecessors[i] = j

     # Find the index of the maximum value in dp (end of the LIS)
     max_len = max(dp)
     end_index = dp.index(max_len)

     # Reconstruct the LIS by backtracking from the end_index
     lis = []
     while end_index is not None:
         lis.append(nums[end_index])
         end_index = predecessors[end_index]

     return lis[::-1]  # Reverse the list to get the correct order

 # Example usage:
 nums = [3, 10, 2, 1, 20]
 lis = longest_increasing_subsequence_dp(nums)
 print(f"Longest Increasing Subsequence: {lis}")
 print(f"Length: {len(lis)}")
 

 Longest Increasing Subsequence: [3, 10, 20]
 Length: 3
 

Explanation:

The longest_increasing_subsequence_dp function calculates the LIS. It initializes a dp array where dp[i] stores the length of the LIS ending at index i. The predecessors array helps reconstruct the actual subsequence. The outer loop iterates through the input list, and the inner loop checks all previous elements. If a previous element is smaller and extending the subsequence would result in a longer subsequence, the dp array is updated. Finally, it backtracks through the predecessors to build the longest increasing subsequence.

Method 2: Patience Sorting Algorithm with Binary Search

The Patience Sorting algorithm combined with binary search provides a more efficient way to find the LIS, reducing the time complexity. This method focuses on maintaining a “tails” array that contains the smallest tail of all increasing subsequences of a given length.

 import bisect

 def longest_increasing_subsequence_patience(nums):
     """
     Finds the longest increasing subsequence using patience sorting and binary search.

     Args:
         nums (list): A list of numbers.

     Returns:
         list: The longest increasing subsequence.
     """
     if not nums:
         return []

     tails = []  # Stores the smallest tail of all increasing subsequences of a given length
     predecessors = {} # Stores predecessors to reconstruct the LIS

     for num in nums:
         if not tails or num > tails[-1]:
             if tails:
                 predecessors[num] = tails[-1]
             tails.append(num)
         else:
             # Find the smallest tail that is >= num using binary search
             index = bisect.bisect_left(tails, num)
             if index > 0:
                 predecessors[num] = tails[index - 1]
             tails[index] = num

     # Reconstruct the LIS by backtracking from the last tail
     lis = []
     last = tails[-1]
     while last is not None:
         lis.append(last)
         last = predecessors.get(last)

     return lis[::-1]  # Reverse the list to get the correct order

 # Example usage:
 nums = [3, 10, 2, 1, 20]
 lis = longest_increasing_subsequence_patience(nums)
 print(f"Longest Increasing Subsequence: {lis}")
 print(f"Length: {len(lis)}")
 

 Longest Increasing Subsequence: [1, 10, 20]
 Length: 3
 

Explanation:

The longest_increasing_subsequence_patience function utilizes patience sorting and binary search. The tails list keeps track of the smallest tail of increasing subsequences. For each number, it either extends the longest subsequence or updates one of the tails to a smaller value, using binary search to find the correct position. The predecessors dictionary helps in reconstructing the LIS by backtracking from the last tail.

Method 3: Recursive Approach with Memoization

A recursive approach can be used to solve the LIS problem, enhanced with memoization to avoid redundant calculations and improve performance. This method directly translates the problem’s recursive nature into code.

 def longest_increasing_subsequence_recursive(nums):
     """
     Finds the longest increasing subsequence using a recursive approach with memoization.

     Args:
         nums (list): A list of numbers.

     Returns:
         list: The longest increasing subsequence.
     """
     def lis_recursive_helper(nums, index, prev, memo):
         if index == len(nums):
             return 0, [] #Base case: end of the list, length 0 and empty subsequence

         if (index, prev) in memo:
             return memo[(index, prev)]

         #Option 1: Exclude current number
         exclude_len, exclude_seq = lis_recursive_helper(nums, index + 1, prev, memo)

         #Option 2: Include current number if it's greater than previous
         if prev is None or nums[index] > nums[prev]:
             include_len, include_seq = lis_recursive_helper(nums, index + 1, index, memo)
             include_len += 1
             include_seq = [nums[index]] + include_seq
         else:
             include_len, include_seq = 0, [] # Cannot include

         #Choose the option that gives the longest sequence
         if include_len > exclude_len:
             memo[(index, prev)] = include_len, include_seq
             return include_len, include_seq
         else:
             memo[(index, prev)] = exclude_len, exclude_seq
             return exclude_len, exclude_seq

     memo = {}
     length, subsequence = lis_recursive_helper(nums, 0, None, memo)
     return subsequence

 # Example usage:
 nums = [3, 10, 2, 1, 20]
 lis = longest_increasing_subsequence_recursive(nums)
 print(f"Longest Increasing Subsequence: {lis}")
 print(f"Length: {len(lis)}")
 

 Longest Increasing Subsequence: [3, 10, 20]
 Length: 3
 

Explanation:

The longest_increasing_subsequence_recursive function uses a recursive helper function lis_recursive_helper with memoization to calculate the LIS. The helper function explores two options for each number: include it in the subsequence (if it’s greater than the previous number) or exclude it. Memoization is used to store the results of subproblems to avoid redundant calculations, significantly improving performance. The base case is when the index reaches the end of the list, returning a length of 0 and an empty subsequence.

Method 4: Numba Optimized Patience Sorting

The Patience Sorting algorithm can be further optimized using Numba’s just-in-time (JIT) compilation to improve performance, especially for large datasets.

 import bisect
 from numba import njit

 @njit
 def longest_increasing_subsequence_numba(nums):
     """
     Finds the longest increasing subsequence using patience sorting and binary search with Numba optimization.

     Args:
         nums (list): A list of numbers.

     Returns:
         list: The longest increasing subsequence.
     """
     if not nums:
         return []

     tails = []  # Stores the smallest tail of all increasing subsequences of a given length
     predecessors = {} # Stores predecessors to reconstruct the LIS

     for num in nums:
         if not tails or num > tails[-1]:
             if tails:
                 predecessors[num] = tails[-1]
             tails.append(num)
         else:
             # Find the smallest tail that is >= num using binary search
             index = bisect.bisect_left(tails, num)
             if index > 0:
                 predecessors[num] = tails[index - 1]
             tails[index] = num

     # Reconstruct the LIS by backtracking from the last tail
     lis = []
     last = tails[-1]
     while last is not None:
         lis.append(last)
         last = predecessors.get(last)

     return lis[::-1]  # Reverse the list to get the correct order

 # Example usage:
 nums = [3, 10, 2, 1, 20]
 lis = longest_increasing_subsequence_numba(nums)
 print(f"Longest Increasing Subsequence: {lis}")
 print(f"Length: {len(lis)}")
 

 Longest Increasing Subsequence: [1, 10, 20]
 Length: 3
 

Explanation:

The longest_increasing_subsequence_numba function optimizes the patience sorting algorithm using Numba’s @njit decorator. This decorator compiles the Python code to machine code, resulting in significant performance improvements, especially for numerical computations. The algorithm remains the same as the patience sorting approach, but the Numba optimization makes it much faster.