最长上升子序列 入门dp练习题

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义变量n和x，用于存储输入的整数数量和每个整数的值
    int n, x;
    // 定义两个向量v和dp，分别用于存储输入的整数序列和动态规划数组
    vector<int> v, dp;
    // 读取整数n，表示输入的整数数量
    cin >> n;
    // 循环读取n个整数，并将其存入向量v中，同时初始化dp数组为1
    for(int i = 0; i < n; i++){
        cin >> x; // 读取一个整数
        v.push_back(x); // 将整数添加到向量v中
        dp.push_back(1); // 初始化dp数组中的对应位置为1
    }
    // 使用双重循环计算最长递增子序列的长度
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            // 如果v[j]大于v[i]，则更新dp[j]为dp[i]+1和dp[j]的最大值
            if(v[j] > v[i]){
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    // 定义变量kk，用于存储最长递增子序列的长度
    int kk = -1;
    // 遍历dp数组，找到其中的最大值，即最长递增子序列的长度
    for(int i = 0; i < n; i++){
        kk = max(kk, dp[i]);
    }
    // 输出最长递增子序列的长度
    cout << kk << endl;
    return 0;
}