互联网推广广告_足球比赛直播2021欧冠决赛_精准网络推广_百度推广关键词和创意

目录

1.题目解析

题目来源

测试用例

2.算法原理

3.实战代码

代码解析

---

注意本题还有一种动态规划的解决方法，贪心的方法就是从动态规划的方法总结而来，各位可以移步博主的另一篇博客先了解一下：动态规划-子序列问题——300.长递增子序列 

1.题目解析

题目来源

300.最长递增子序列——力扣

测试用例

2.算法原理

 

贪心思路 

具体算法 

此时的时间复杂度是O(N^2)，与动态规划一样，那么我们就需要继续优化，这里插入dp表后判断插入位置可以使用二分查找来进行优化，优化后时间复杂度就是O(N*logN)  

3.实战代码

class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp;dp.push_back(nums[0]);for(int i = 1;i < n;i++){if(nums[i] > dp.back()){dp.push_back(nums[i]);}else{int left = 0,right = dp.size();while(left < right){int mid = (left + right) >> 1;if(nums[i] > dp[mid])  left = mid + 1;else right = mid;}dp[left] = nums[i];}}return dp.size();}
};

代码解析