Find the Longest Increasing Subsequence in a List

Finding the longest increasing subsequence (LIS) within a list is a classic computer science problem with applications in various fields, from bioinformatics to financial modeling. This post will explore efficient ways to solve this problem using Python.

Understanding the Problem

Given a list of numbers, the goal is to find the longest subsequence where each element is strictly greater than the preceding element. For example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 101] (or any other LIS of length 4)

Note that the elements of the subsequence do not need to be contiguous in the original list.

Approach 1: Dynamic Programming

Dynamic programming provides an efficient solution with a time complexity of O(n log n), where n is the length of the input list. The core idea is to maintain a list tails where tails[i] represents the smallest tail of all increasing subsequences of length i+1.

Here’s the Python code:

def longest_increasing_subsequence(nums):
    if not nums:
        return []

    tails = []  # Stores the smallest tail of all increasing subsequences of a given length
    predecessors = {} #Keeps track of predecessors for reconstructing the subsequence

    for num in nums:
        if not tails or num > tails[-1]:
            if tails:
                predecessors[num] = tails[-1]
            tails.append(num)
        else:
            # Find the rightmost tail that is greater than or equal to the current number
            idx = 0
            l, r = 0, len(tails) -1
            while l <= r:
                mid = (l+r)//2
                if tails[mid] < num:
                    idx = mid + 1
                    l = mid + 1
                else:
                    r = mid -1

            if idx > 0:
                predecessors[num] = tails[idx-1]
            tails[idx] = num

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

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


#Example
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums)) # Output: [2, 3, 7, 101]

nums = [0,1,0,3,2,3]
print(longest_increasing_subsequence(nums)) # Output: [0, 1, 2, 3]

nums = [7,7,7,7,7,7,7]
print(longest_increasing_subsequence(nums)) # Output: [7]

This improved version uses binary search to find the correct position in tails, significantly optimizing the search process.

Approach 2: (Less Efficient) Simple Recursive Approach (for smaller inputs only)

A simpler, but less efficient (O(2ⁿ)) approach involves recursion. This is suitable only for smaller input lists due to its exponential time complexity. We won’t look into the code here as it is significantly less efficient than the dynamic programming approach.