最长递增子序列(LIS)算法详解

动态规划与贪心+二分查找两种解法

什么是LIS问题？

最长递增子序列(Longest Increasing Subsequence, LIS)问题是指：在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地长。

例如：对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 101]，长度为4。

解法一：动态规划(DP)

核心思想

动态规划解法的核心思想是：对于序列中的每个元素，计算以该元素为结尾的最长递增子序列的长度。这个长度可以通过检查该元素之前的所有元素来确定：如果之前的某个元素小于当前元素，那么可以将当前元素附加到以该元素结尾的子序列后面，形成一个更长的子序列。

算法步骤

  1. 初始化一个dp数组，dp[i]表示以第i个元素为结尾的最长递增子序列的长度，初始值全部设为1（每个元素本身就是一个长度为1的子序列）
  2. 对于每个位置i(从1到n-1)，遍历所有j(从0到i-1)：
  3. 如果a[i] > a[j]，说明a[i]可以接在a[j]后面形成一个更长的递增子序列，更新dp[i] = max(dp[i], dp[j] + 1)
  4. 遍历dp数组，找到最大值，即为最长递增子序列的长度

时间复杂度分析

时间复杂度：O(n²)，因为有两层循环嵌套

空间复杂度：O(n)，需要一个长度为n的dp数组

代码实现

动态规划解法代码
// 动态规划解法 - 时间复杂度O(n²)
#include <bits/stdc++.h>
using namespace std;

int n, a[10005], ans;
int dp[10005]; // dp[i]：以i结尾的最长上升子序列的长度

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 初始化dp数组，每个元素至少可以单独成为一个子序列
    for (int i = 0; i < n; i++)
        dp[i] = 1;
    
    // 动态规划过程
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++) // 枚举以i为结尾节点的前一个点j
        {
            if (a[i] > a[j]) // i可以接到j后面
            {
                // 长度是以j为结尾的最长上升子序列加1，打擂台取最大值
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    // 找到dp数组中的最大值
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
        
    cout << ans << endl;
    return 0;
}

解法二：贪心+二分查找

核心思想

贪心+二分查找解法的核心思想是：维护一个tail数组，其中tail[i]表示长度为i+1的所有递增子序列中末尾元素的最小值。通过这种方式，我们可以确保tail数组是一个递增序列，从而可以使用二分查找来优化搜索过程。

算法步骤

  1. 初始化tail数组，将第一个元素放入tail[0]，并设置len=1
  2. 对于序列中的每个元素a[i]：
  3. 如果a[i]大于tail数组的最后一个元素，说明可以扩展最长递增子序列，将a[i]添加到tail末尾，len++
  4. 否则，在tail数组中查找第一个大于等于a[i]的元素位置，并用a[i]替换该位置的值
  5. 最终len的值就是最长递增子序列的长度

时间复杂度分析

时间复杂度：O(n log n)，每个元素处理一次，每次处理使用二分查找(O(log n))

空间复杂度：O(n)，需要一个长度为n的tail数组

代码实现

贪心+二分查找解法代码
// 贪心+二分查找解法 - 时间复杂度O(n log n)
#include <bits/stdc++.h>
using namespace std;

int n, a[1000005], ans;
// tail[i]:长度为i+1的最长上升子序列的末尾元素的最小值
int tail[1000005];

// 在tail数组中查找第一个大于等于x的元素的位置
int binary_search(int start, int len, int x)
{
    int l = start, r = len - 1, res = len; // res = len表示没有找到
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (tail[mid] < x)
            l = mid + 1;
        else
        {
            res = mid;
            r = mid - 1;
        }
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 初始化tail数组
    tail[0] = a[0];
    int len = 1; // tail数组的长度
    
    for (int i = 1; i < n; i++)
    {
        if (a[i] > tail[len - 1]) // 如果当前元素大于tail数组的末尾元素
        {
            tail[len] = a[i]; // 则直接加入tail数组
            len++; // tail数组的长度加1
        }
        else
        {
            // 在tail数组中查找第一个大于等于a[i]的元素的位置
            int pos = binary_search(0, len, a[i]);
            tail[pos] = a[i];
        }
    }
    
    cout << len << endl;
    return 0;
}

两种解法对比

特性 动态规划解法 贪心+二分查找解法
时间复杂度 O(n²) O(n log n)
空间复杂度 O(n) O(n)
核心思想 计算以每个元素结尾的最长递增子序列长度 维护不同长度递增子序列的最小末尾元素
适用场景 小规模数据(n ≤ 10⁴) 大规模数据(n ≤ 10⁶)
能否重构LIS 可以，通过dp数组回溯 不能直接得到LIS，只能得到长度

选择建议

1. 对于小规模数据(n ≤ 10⁴)，两种方法都可以使用，动态规划方法更直观易懂

2. 对于大规模数据(n ≤ 10⁶)，必须使用贪心+二分查找方法，否则会超时

3. 如果需要重构最长递增子序列本身，动态规划方法更合适