数据结构与算法之最长递增子序列

最长递增子序列（Longest Increasing Subsequence，LIS）是指在一个序列中找到一个最长的子序列使得这个子序列中的所有元素都按照从小到大的顺序排列。LIS问题在计算机科学中有广泛的应用，比如在数据压缩、机器学习、自然语言处理等领域。

LIS问题可以使用动态规划算法解决。设数组dp[i]表示以第i个元素为结尾的最长递增子序列的长度。则dp[i]的值可以根据dp[0], dp[1],…, dp[i-1]中的最大值得出：

dp[i] = max(dp[j]+1) for all j<i and nums[j]<nums[i]

其中nums是原序列。即dp[i]等于所有满足nums[j]<nums[i]的dp[j]的最大值加1。最终的LIS长度为dp数组中的最大值。

动态规划算法的时间复杂度为O(n^2)，其中n为原序列的长度。还有一种基于二分查找的优化算法，可以将时间复杂度降到O(nlogn)。这种算法的思想是维护一个数组d，d[i]表示长度为i的最长递增子序列的末尾元素的最小值。遍历原序列时，对于每个元素，如果它比d中最后一个元素大，则将它加入d的末尾；否则，在d中二分查找第一个比它大的元素，并将其替换为当前元素。最终d的长度就是最长递增子序列的长度。

一、C 实现 最长递增子序列 及代码详解

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是一个经典的动态规划问题。给定一个整数序列，找到其中的一个最长递增子序列，使得子序列中的所有元素都按照递增的顺序排序。

C 语言实现最长递增子序列的代码如下：

#include <stdio.h>
#include <stdlib.h>

int lis(int arr[], int n) {
    int* dp = (int*) calloc(n, sizeof(int)); // 动态分配一个大小为 n 的数组 dp，用于存储每个位置上最长递增子序列的长度
    int max_len = 1; // 初始值为 1，因为单个元素也算一个最长递增子序列
    dp[0] = 1; // 第一个元素的最长递增子序列长度为 1

    for (int i = 1; i < n; i++) { // 遍历整个数组
        int cur_max_len = 0; // 当前位置的最长递增子序列长度
        for (int j = 0; j < i; j++) { // 在 i 之前找到比 arr[i] 小的元素，并更新 dp[i]
            if (arr[i] > arr[j]) {
                if (dp[j] > cur_max_len) {
                    cur_max_len = dp[j];
                }
            }
        }
        dp[i] = cur_max_len + 1; // 最长递增子序列长度为当前位置最大的长度加上 1
        if (dp[i] > max_len) { // 更新全局最长递增子序列长度
            max_len = dp[i];
        }
    }

    free(dp); // 释放动态分配的内存
    return max_len; // 返回最长递增子序列的长度
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = lis(arr, n);
    printf("The length of the longest increasing subsequence is %d\n", result);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

代码详解：

1. 引入必要的头文件：stdio.h 和 stdlib.h。前者是用于输出结果，后者是用于动态分配数组空间。

2. 定义 lis 函数，用于计算最长递增子序列的长度。参数列表包括整数数组 arr 和数组长度 n。

3. 动态分配一个大小为 n 的数组 dp，用于存储每个位置上最长递增子序列的长度。

   int* dp = (int*) calloc(n, sizeof(int));
   1

   这里使用了 calloc 函数进行动态分配空间，与 malloc 不同的是，calloc 函数会将分配到的内存清零，避免出现未初始化的问题。

4. 设置变量 max_len，用于记录最长递增子序列的长度，初始值为 1，因为单个元素也算一个最长递增子序列。同时，记录数组第一个元素的最长递增子序列长度为 1。

   int max_len = 1;
   dp[0] = 1;
   1
   2

5. 使用两个嵌套循环遍历整个数组，计算每个位置上的最长递增子序列长度。外层循环变量 i 表示当前位置，内层循环变量 j 表示在 i 之前的位置。

   for (int i = 1; i < n; i++) {
       int cur_max_len = 0;
       for (int j = 0; j < i; j++) {
           ...
       }
       ...
   }
   1
   2
   3
   4
   5
   6
   7

6. 在内层循环中，判断当前位置 i 是否可以接在 j 后面形成递增子序列。如果可以，则更新 cur_max_len，使其等于 j 位置的最长递增子序列长度，如果大于当前位置的最长递增子序列长度，则更新当前位置的最长递增子序列长度。

   if (arr[i] > arr[j]) {
       if (dp[j] > cur_max_len) {
           cur_max_len = dp[j];
       }
   }
   1
   2
   3
   4
   5

   dp[j] 表示在 j 位置上的最长递增子序列长度。

7. 最后，将当前位置的最长递增子序列长度设置为 cur_max_len + 1，表示当前位置可以接在 j 位置的最长递增子序列后面，形成更长的递增子序列。如果当前位置的最长递增子序列长度大于全局最长递增子序列长度，则更新 max_len。

   dp[i] = cur_max_len + 1;
   if (dp[i] > max_len) {
       max_len = dp[i];
   }
   1
   2
   3
   4

8. 循环遍历结束后，释放动态分配的数组 dp。

   free(dp);
   1

9. 在 main 函数中，定义一个整数数组 arr，并计算其长度 n。调用 lis 函数，将返回的最长递增子序列长度赋值给变量 result，最后输出结果。

   int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
   int n = sizeof(arr) / sizeof(arr[0]);
   int result = lis(arr, n);
   printf("The length of the longest increasing subsequence is %d\n", result);
   1
   2
   3
   4

二、C++ 实现 最长递增子序列 及代码详解

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是指在一个无序的序列中，找到一个子序列使得这个子序列中的元素单调递增，并且这个子序列的长度最长。

以下是 C++ 中实现 LIS 的代码和详细解释。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int a[N], dp[N], pre[N];
int n;

// 二分查找子程序
int binary_search(int l, int r, int x) {
    while (l < r) {
        int mid = l + r >> 1;
        if (dp[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}

void LIS() {
    memset(dp, 0x3f, sizeof(dp)); // 初始化为正无穷
    dp[0] = a[0]; // dp 数组的初始值为第一个元素 a[0]
    int len = 1; // dp 数组的长度为 1

    for (int i = 1; i < n; i++) {
        int pos = binary_search(0, len, a[i]); // 二分查找 dp 数组中第一个大于等于 a[i] 的数的位置
        dp[pos] = a[i];
        pre[i] = pos > 0 ? pre[pos-1] : -1; // 记录 a[i] 的前驱位置
        len = max(len, pos+1);
    }

    cout << "LIS 的长度为：" << len << endl;
    cout << "其中一个 LIS 为：";
    int k = pre[n-1];
    while (k != -1) {
        cout << a[k] << " ";
        k = pre[k];
    }
    cout << endl;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    LIS();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

代码解释：

1. 首先定义了一个数组 a 存储输入的序列，以及三个辅助数组：dp、pre 和最大长度 len。

2. dp 数组表示以 a[i] 结尾的 LIS 长度，pre 数组存储 a[i] 的前驱位置，即 dp 数组中第一个小于 dp[i] 的位置。

3. 需要定义一个二分查找子程序，用于查找 dp 数组中第一个大于等于 a[i] 的数的位置，可以看出这里采用的是单调不降的策略。

4. LIS() 函数中，首先将 dp 数组初始化为正无穷，dp[0] 的值为 a[0]，len 的初始值为 1。

5. 然后从 1 到 n-1 遍历数组 a，每次查找 dp 数组中第一个大于等于 a[i] 的数的位置 pos，将 a[i] 赋值给 dp[pos]。

6. 同时更新 pre[i] 的值，若 pos 大于 0，则 pre[i] 的值为 pre[pos-1]，否则为 -1。

7. 更新 len 的值，即为 max(len, pos+1)。

8. 最后输出 LIS 的长度 len，以及其中一个 LIS。

9. 在输出一个 LIS 的过程中，从 pre[n-1] 开始倒序遍历 pre 数组，并输出相应的 a[i] 的值。

三、Java 实现 最长递增子序列 及代码详解

最长递增子序列问题指的是在给定的序列中找到一个最长的严格递增的子序列。例如，对于序列 [1, 3, 2, 6, 4, 5, 7]，其最长递增子序列为 [1, 2, 4, 5, 7]。

Java 实现最长递增子序列的算法可以用动态规划来解决，具体步骤如下：

1. 定义状态：我们用 $dp[i]$ 表示以第 $i$ 个元素为结尾的最长递增子序列的长度。

2. 定义状态转移方程：状态转移方程为 d p [ i ] = max ⁡ { d p [ j ] + 1 } dp[i] = \max\{dp[j]+1\} dp[i]=max{dp[j]+1}，其中 $j<i$ 且 $nums[j]<nums[i]$。

3. 初始化：初始状态都为 1，即对于 $1\le i\le n$，$dp[i]=1$。

4. 最终结果为 max ⁡ { d p [ i ] } \max\{dp[i]\} max{dp[i]}，$1\le i\le n$。

下面是 Java 实现代码：

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    int res = 1;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。