Efficient Algorithm for Finding the Longest Increasing Subsequence [duplicate]

Question

I'm working on a project where I need to find the longest increasing subsequence (LIS) from a given array of integers. However, the array can be quite large, so I'm looking for an efficient algorithm to solve this problem.

I've looked into dynamic programming solutions like the O(n^2) approach using an array to store the length of the LIS ending at each index, but I'm wondering if there's a more efficient algorithm available.

Could someone please suggest an efficient algorithm or point me toward resources that discuss optimized approaches for finding the LIS?

Thank you in advance for your help!

Answer 1

• It depends on the size of your input.
• If it is too large, then caching can be used.
• Binary search can be implemented with the dynamic programming.

Python

import random

def longest_increasing_subsequence(A):
    def binary_search(lo, hi, target):
        while lo <= hi:
            mid = (lo + hi) // 2
            if dp[mid] >= target:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

    dp = [float('inf')] * len(A)
    lcs = 0
    for num in A:
        lo, hi = 0, lcs
        lo = binary_search(lo, hi, num)
        dp[lo] = num
        lcs = max(lcs, lo + 1)

    return lcs


random.seed(0)
A = [random.randint(500, 1000) for _ in range(1000000)]
print(longest_increasing_subsequence(A))

C++

#include <cstdint>
#include <vector>
#include <algorithm>
#include <iostream>
#include <random>

static const int longest_increasing_subsequence(
    const std::vector<int> &A)
{
    std::vector<int> longest;

    for (std::size_t index = 0; index < A.size(); index++)
    {
        const auto iter = std::lower_bound(longest.begin(), longest.end(), A[index]);

        if (iter == longest.end())
        {
            longest.emplace_back(A[index]);
        }
        else
        {
            *iter = A[index];
        }
    }

    return longest.size();
}

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(500, 1000);
    const int input_size = 10000000;
    std::vector<int> random_array;
    random_array.reserve(input_size);
    for (int i = 0; i < input_size; ++i)
    {
        random_array.push_back(dis(gen));
    }

    int lis_length = longest_increasing_subsequence(random_array);
    std::cout << "Length of longest increasing subsequence: " << lis_length << std::endl;

    return 0;
}