# [LeetCode] Longest Increasing Subsequence 最长递增子序列

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

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

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> ends{nums[0]};
for (auto a : nums) {
if (a < ends[0]) ends[0] = a;
else if (a > ends.back()) ends.push_back(a);
else {
int left = 0, right = ends.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (ends[mid] < a) left = mid + 1;
else right = mid;
}
ends[right] = a;
}
}
return ends.size();
}
};

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

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
auto it = lower_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}　　　　　 　return v.size();
}
};

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
if (find(v.begin(), v.end(), a) != v.end()) continue;
auto it = upper_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}
return v.size();
}
};

|
1月前
|

20 1
|
26天前
|

7 0
|
1月前
|
Java

23 1
|
2月前
leetcode代码记录（最长连续递增序列
leetcode代码记录（最长连续递增序列
25 2
|
2月前
leetcode代码记录（最长递增子序列
leetcode代码记录（最长递增子序列
19 1
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
30 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
36 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
27 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
24 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
28 1