🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

例如：[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 

二、测试样例

输入：nums = [10,9,2,5,3,7,101,18]

输出：4

说明：最长递增子序列是 [2,3,7,101]，当然，[2, 5, 7, 101] 也是最长递增子序列，因此长度为 4 。

三、算法思路

本题考查动态规划单调递增子序列算法，首先需要注意的是，本题单调递增并非指连续的单调递增，只要满足 ai < aj < ak < al ……< ay，其中，i < j < k < l < ……< y。

可以使用一个数组存储严格单调递增的序列，依次遍历数组，将当前元素插入到单调递增的子序列中，插入后保持子序列依然是单调递增的，直到插入最后一个元素。此时，数组中存储的严格单调递增子序列的长度即是整个序列的严格单调递增子序列的长度。

四、代码实现

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(!nums.size()) return 0;
        vector<int> lis;
        lis.push_back(nums[0]);
        for(int i = 1; i < (int)nums.size(); ++i) {
            int tmp = nums[i];
            int idx = lower_bound(lis.begin(), lis.end(), tmp) - lis.begin();
            if(idx == (int)lis.size()) {
                lis.push_back(tmp);
            } else {
                lis[idx] = tmp;
            }
        }
        return lis.size();
    }
};

int main()
{
    int a[10] = {10,9,2,5,3,7,101,18};
    vector<int> nums(a, a+8);
    Solution obj;
    cout<<obj.lengthOfLIS(nums)<<endl;
    return 0;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度为：O(nlogn)，n 为子序列的长度，算法只有一层 for 循环，每次循环需要执行一次二分查找，故时间复杂度为O(nlogn)。 

5.2 空间复杂度

空间复杂度为：O(n)，n 为子序列长度，实际的空间复杂度为严格单调递增子序列的长度，最坏情况下为 O(n)。

六、总结

本题考查对动态规划最长单调递增子序列的理解，同时也要对二分查找算法有一定了解。

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

​