• 300. 最长递增子序列

    1. 背

    dp[i]表示有i个字符时最长递增子序列的最小末尾。长度为i的最长递增子序列可能有多个，但是最小末尾只能有一个。例如12378，长度为4的有1237和1238，但是最小的就是7。这么做的目的是为了能让每次更新dp的时候能用更高的效率。传统的dp手段每遍历一次就会遍历一次dp数组，但是用这种最小末尾的可以用二分的方式更新这个dp，因此复杂度就变成了nlogn

    2. 答案

    class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n = static_cast(nums.size());
        vectordp(n+1,INT_MAX);
        dp[1] = nums[0];
        for(int i=1;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    class Solution {
public:
    int lengthOfLIS(vector& nums) { int n = static_cast(nums.size());
        vectordp;
        dp.push_back(nums[0]);
       
        for(int i=1;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
  • 相关阅读:
    C Primer Plus(6) 中文版 第10章 数组和指针 10.7 指针和多维数组
    SQL关于日期的计算合集
    Easy3D 曲面网格数据的读取与写入
    2023年亚太杯数学建模思路 - 案例：异常检测
    内存空间的分配与回收
    尚医通（四）
    第5章 Object Interactive
    react-通过useRef完成倒计时60秒发送验证码效果
    本地域名 127.0.0.1 / localhost
    【数据结构与算法——C语言】“串操作与算法”之“找出最长串及其长度”
  • 原文地址：https://blog.csdn.net/qigezuishuaide/article/details/127712651