*Leetcode 300. Longest Increasing Subsequence

本文主要是介绍*Leetcode 300. Longest Increasing Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/longest-increasing-subsequence/description/

经典的LIS。

O(n^2)的解法还是很直观的

class Solution {
public:int lengthOfLIS(vector<int>& nums) {// int dp[nums.size()];int ans = 0;vector <int> dp(nums.size(), 0);for (int i = 0; i < nums.size(); i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = max(dp[j]+1, dp[i]) ;}ans = max(ans, dp[i]);}return ans;}
};

优化算法很有意思：https://leetcode.com/problems/longest-increasing-subsequence/discuss/74848/9-lines-C++-code-with-O(NlogN)-complexity

int lengthOfLIS(vector<int>& nums) {vector<int> res;for(int i=0; i<nums.size(); i++) {auto it = std::lower_bound(res.begin(), res.end(), nums[i]);if(it==res.end()) res.push_back(nums[i]);else *it = nums[i];}return res.size();
}

这篇关于*Leetcode 300. Longest Increasing Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---