线性动态规划-最长递增子序列(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;
}