Efficient search for longest ascending subsequence in large lists of integers with Python

How can I develop an efficient and scalable algorithm implementation in Python to find the longest ascending subsequence in a large list of integers? I have a list with millions of elements, and my current solution is too slow. Here is my current Python code as a starting point:

def longest_increasing_subsequence(nums):
    n = len(nums)
    lis = [1] * n
    for i in range(1, n):
        for j in range(0, i):
            if nums[i] > nums[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    max_length = max(lis)
    result = []

    for i in range(n - 1, -1, -1):
        if lis[i] == max_length:
            result.append(nums[i])
            max_length -= 1

    return result[::-1]

I have noticed that this code is very slow for large input lists. Is there any way to optimize this algorithm or even use another algorithm that is better suited to find the longest ascending subsequence in a large list of integers? I am open to any ideas to improve the running time and memory requirements. Thanks in advance!

You can find the longest increasing subsequence in O(n log n) time with an approach that combines dynamic programming (your current approach) with binary search (in this case via the <code>bisect.<b>bisect_left</b></code> method):

import bisect

def longest_increasing_subsequence(nums: list[int]) -> list[int]:
    if not nums:
        return []
    piles = []
    indices = [0 for _ in range(len(nums))]
    predecessors = [None for _ in range(len(nums))]
    for i, num in enumerate(nums):
        pile = bisect.bisect_left(piles, num)
        if pile == len(piles):
            piles.append(num)
        else:
            piles[pile] = num
        indices[pile] = i
        predecessors[i] = indices[pile - 1] if pile else None
    last_index = indices[len(piles) - 1]
    longest_subsequence = []
    while last_index is not None:
        longest_subsequence.append(nums[last_index])
        last_index = predecessors[last_index]
    return longest_subsequence[::-1]

Example Usage:

>>> longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])
[2, 3, 7, 18]
>>> longest_increasing_subsequence([0, 1, 0, 3, 2, 3])
[0, 1, 2, 3]
>>> longest_increasing_subsequence([7, 7, 7, 7, 7, 7])
[7]

As said above, your solution is in quadratic time complexity. However according to wikipedia the optimal solution can be found in O(n log(n)) time complexity.

I fixed a code I found here to get a function that runs in optimal time complexity and I tested that the results are consistent with your original function:

# Binary search
def GetCeilIndex(arr, T, l, r, key):
    while r - l > 1:
        m = l + (r - l) // 2
        if arr[T[m]] >= key:
            r = m
        else:
            l = m

    return r


def LongestIncreasingSubsequence(arr):
    n = len(arr)

    # Initialized with 0
    tailIndices = [0 for i in range(n + 1)]

    # Initialized with -1
    prevIndices = [-1 for i in range(n + 1)]

    # it will always point
    # to empty location
    length = 1
    for i in range(1, n):
        if arr[i] < arr[tailIndices[0]]:
            # new smallest value
            tailIndices[0] = i

        elif arr[i] > arr[tailIndices[length - 1]]:
            # arr[i] wants to extend
            # largest subsequence
            prevIndices[i] = tailIndices[length - 1]
            tailIndices[length] = i
            length += 1

        else:
            # arr[i] wants to be a
            # potential condidate of
            # future subsequence
            # It will replace ceil
            # value in tailIndices
            pos = GetCeilIndex(arr, tailIndices, -1, length - 1, arr[i])

            prevIndices[i] = tailIndices[pos - 1]
            tailIndices[pos] = i

    res = []
    i = tailIndices[length - 1]
    while len(res) < length:
        res.append(arr[i])
        i = prevIndices[i]
    res.reverse()

    return res