寻找最长递增子序列的高效算法

Question

我正在开发一个项目，需要从给定的整数数组中找到最长的递增子序列（LIS）。然而，数组可能非常大，所以我正在寻找一种有效的算法来解决这个问题。

我研究了动态编程解决方案，例如使用数组来存储以每个索引结尾的 LIS 长度的 O(n^2) 方法，但我想知道是否有更有效的算法可用。

有人可以建议一种有效的算法或向我指出讨论寻找 LIS 的优化方法的资源吗？

提前感谢您的帮助！

Answer 1

• 这取决于您输入的大小。
• 如果太大，可以使用缓存。
• 二分查找可以通过动态规划来实现。

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;
}