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(vectorintnums){intnnums.size();vectorintf(n);for(inti0;in;i){f[i]0;for(intj0;ji;j){if(nums[j]nums[i]){f[i]max(f[i],f[j]);}}f[i];}returnranges::max(f);}};难度等级⭐️⭐️⭐️⭐️1~10星以个人刷题整理为目的如若侵权请联系删除~