c++最长上升子序列

Question

最长上升子序列
Description

给出一个由n个数组成的序列A[1..n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a1<a2<……<am且A[a1]<A[a2]<……<A[am]。

Input

两行：

第1行：整数n (1<=n<=1000)

第2行：n个整数 （int范围内），空格隔开。

Output

一行：一个整数，即最长上升子序列长度。

Sample Input 1

10
63 11 21 36 28 20 57 37 82 4
Sample Output 1

5

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

要解决这个问题，我们可以使用动态规划的方法来找到最长上升子序列（LIS）。动态规划通过构建一个数组来存储到目前为止的最优解，并逐步更新这个数组以找到全局最优解。

动态规划方法

1. 初始化一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。
2. 将 dp 数组中的所有元素初始化为1，因为每个元素本身都可以构成一个长度为1的子序列。
3. 遍历数组 A，对于每一个元素 A[j]，再遍历其前面的所有元素 A[i]，如果 A[i] < A[j]，则更新 dp[j] 的值为 max(dp[j], dp[i] + 1)。
4. 最后，遍历 dp 数组，找出最大值，这就是最长上升子序列的长度。

下面是实现上述算法的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    for(int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    vector<int> dp(n, 1); // 初始化dp数组，所有元素都为1
    
    // 动态规划填充dp数组
    for(int j = 1; j < n; ++j) {
        for(int i = 0; i < j; ++i) {
            if(A[i] < A[j]) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    
    // 找出dp数组中的最大值
    int maxLength = *max_element(dp.begin(), dp.end());
    
    cout << maxLength << endl;
    
    return 0;
}

解释

1. 输入处理：首先读取整数 n 和数组 A。
2. 动态规划数组初始化：dp 数组初始化为1，表示每个元素本身可以构成一个长度为1的子序列。
3. 状态转移：对于每个元素 A[j]，检查它之前的所有元素 A[i]，如果 A[i] < A[j]，则更新 dp[j] 的值。
4. 结果输出：最后输出 dp 数组中的最大值，即最长上升子序列的长度。

这种方法的时间复杂度是 O(n^2)，适用于题目给定的范围 1 <= n <= 1000。