hot 100 300.最长递增子序列

问题描述

给你一个整数数组nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。

样例输入

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

样例输出

4

评测用例规模与约定

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

解析

分析问题：
就正常人思维想的话还是暴力从每一个数开始往后遍历看递增的序列长度，但是这样做肯定不对了，因为序列不是有序的，可能大的在前面，长度是和后面小的连起来才最大。所以又是要枚举所有情况从i位置开始和从后面每一位开始的递增长度，这样时间会超时，时间复杂度太大了。
怎么做：
我们想想动态规划了，n*m 递推肯定不会超时，怎么办；
f[i]表示以i位置为结尾的最长递增子序列长度，那么面对前面小于的元素，就是从那个状态过来的所以是f[i]=max(f[i],f[j]);最后加1因为不知道从那个过来是最大的先选出最大的再加1；
还想优化空间的话可以用贪心+二分的思想看灵神的视频

参考程序

classSolution{public:intlengthOfLIS(vector<int>&nums){intn=nums.size();vector<int>f(n);for(inti=0;i<n;i++){f[i]=0;for(intj=0;j<i;j++){if(nums[j]<nums[i]){f[i]=max(f[i],f[j]);}}f[i]++;}returnranges::max(f);}};

难度等级

⭐️⭐️⭐️⭐️（1~10星）
以个人刷题整理为目的，如若侵权，请联系删除~