线性动态规划-最长递增子序列(LIS)

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-04-08 21:39:55
 * 最后修改: 2024-12-24 19:14:27
 * 文件描述: 最长上升子序列  O(N^2)
****************************************************************/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, ans; // N: 数组长度, ans: 存储最长递增子序列的长度
    cin >> N; // 输入数组长度

    // 定义数组A存储输入的元素，F存储以第i个元素为结尾的最长递增子序列长度
    vector<int> A(N + 1), F(N + 1);

    // 输入数组元素（从1到N存储）
    for (int i = 1; i <= N; i++) cin >> A[i];

    F[1] = 1; // 初始化第一个元素的最长递增子序列长度为1
    ans = 1;  // 初始化答案为1（至少有一个元素时，长度为1）

    // 从第2个元素开始，逐步计算以每个元素为结尾的最长递增子序列长度
    for (int i = 2; i <= N; i++) {
        F[i] = 1; // 初始时，当前元素自身可单独形成子序列，长度为1

        // 遍历当前元素之前的所有元素，尝试找到最长的递增子序列
        for (int j = 1; j <= i - 1; j++) {
            // 如果前面的元素A[j]小于等于当前元素A[i]，并且F[j]+1比当前F[i]大
            if (A[j] <= A[i] && F[j] + 1 > F[i]) 
                F[i] = F[j] + 1; // 更新F[i]，表示将A[i]接在以A[j]结尾的序列后
        }

        // 更新全局答案：取当前元素的F[i]和ans的较大值
        if (F[i] > ans) ans = F[i];
    }

    cout << ans << endl; // 输出最长递增子序列的长度
}

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-24 15:43:12
 * 最后修改: 2024-12-24 20:08:32
 * 文件描述: 最长上升子序列  O(nlongn)
****************************************************************/

#include <iostream>
#include <vector>
#include <algorithm> // 包含 lower_bound 函数
using namespace std;

int main() {
    int N;
    cin >> N; // 输入数组长度
    vector<int> nums(N); // 定义数组 nums
    for (int i = 0; i < N; i++) cin >> nums[i]; // 输入数组元素

    // 用于存储构造的最长递增子序列的最优结构（长度等价的最优序列）
    vector<int> ans;
    ans.push_back(nums[0]); // 初始化，放入第一个元素

    for (int i = 1; i < N; i++) {
        if (nums[i] > ans.back()) {
            // 如果当前元素比 ans 的最后一个元素大，直接追加到 ans
            ans.push_back(nums[i]);
        } else {
            // 如果当前元素不比 ans 的最后一个元素大
            // 使用 lower_bound 找到 ans 中第一个大于等于 nums[i] 的位置
            //手工二分查找也可以
            auto it = lower_bound(ans.begin(), ans.end(), nums[i]);

            // 替换该位置的元素为 nums[i]
            *it = nums[i];
        }
    }

    // 输出 ans 的长度，即最长递增子序列的长度
    cout << ans.size() << endl;

    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2026-06-21 15:43
 * 最后修改: 2026-06-21 15:44
 * 文件描述: 输出最长上升子序列的长度和一条实际序列，时间复杂度 O(n log n)
 * 核心算法: 用最小结尾值数组二分维护长度，同时记录前驱下标并从最后结点倒推恢复序列。
****************************************************************/

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 空序列没有上升子序列，直接输出长度 0。
    if (n <= 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // tailValue 不一定是一条真实子序列。
    // 它只负责维护：长度为 len 的上升子序列，结尾最小可以是多少。
    // 结尾越小，后面越容易接上更大的数。
    vector<int> tailValue;

    // tailIndex[len - 1] 记录 tailValue[len - 1] 来自原数组的哪个位置。
    // 恢复真实序列时，必须用下标连接，不能直接输出 tailValue。
    vector<int> tailIndex;

    // previous[i] 记录 a[i] 前面接的是哪个元素。
    // 例如 previous[i] = j，表示恢复序列时 a[j] 在 a[i] 前面。
    vector<int> previous(n, -1);

    for (int i = 0; i < n; i++) {
        // 找到第一个 >= a[i] 的位置。
        // pos 表示 a[i] 可以作为长度 pos + 1 的上升子序列结尾。
        int pos = lower_bound(tailValue.begin(), tailValue.end(), a[i]) - tailValue.begin();

        // 如果 a[i] 不是长度 1 的开头，那么它前面应该接上
        // 当前“长度为 pos 的最优结尾”的那个元素。
        if (pos > 0) previous[i] = tailIndex[pos - 1];

        if (pos == (int)tailValue.size()) {
            // a[i] 比所有最优结尾都大，可以把 LIS 长度扩展 1。
            tailValue.push_back(a[i]);
            tailIndex.push_back(i);
        } else {
            // 用更小或相等的 a[i] 替换原来的结尾值。
            // 这样不改变当前长度，但让后续更容易继续接数。
            tailValue[pos] = a[i];
            tailIndex[pos] = i;
        }
    }

    // tailIndex.back() 是最长长度对应的最后一个元素下标。
    // 沿着 previous 一直往前走，就能得到一条真实 LIS，只是顺序是反的。
    vector<int> lis;
    for (int cur = tailIndex.back(); cur != -1; cur = previous[cur]) {
        lis.push_back(a[cur]);
    }
    reverse(lis.begin(), lis.end());

    cout << lis.size() << endl;
    for (int i = 0; i < (int)lis.size(); i++) {
        if (i > 0) cout << ' ';
        cout << lis[i];
    }
    cout << endl;

    return 0;
}