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

2021年09月15日 阅读数：2

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

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.java

Your algorithm should run in O(n2) complexity.python

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

Java: DPurl

```public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = 1;
int[] lens = new int[nums.length];
Arrays.fill(lens, 1);
for(int i=1; i<nums.length; i++) {
for(int j=0; j<i; j++) {
if (nums[j]<nums[i]) lens[i] = Math.max(lens[i], lens[j]+1);
}
max = Math.max(max, lens[i]);
}
return max;
}
}
```

Java:  BS

```public class Solution {
public int lengthOfLIS(int[] nums) {
int[] increasing = new int[nums.length];
int size = 0;
for(int i=0; i<nums.length; i++) {
int left=0, right=size-1;
while (left<=right) {
int m=(left+right)/2;
if (nums[i] > increasing[m]) left = m + 1;
else right = m - 1;
}
increasing[left] = nums[i];
if (left==size) size ++;
}
return size;
}
}
```

Java: TreeSet

```public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = 1;
TreeSet<Integer> ts = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return Integer.compare(nums[i1], nums[i2]);
}
});
int[] lens = new int[nums.length];
Arrays.fill(lens, 1);
for(int i=0; i<nums.length; i++) {
if (ts.contains(i)) ts.remove(i);
lens[i] = Math.max(lens[i], lens[head] + 1);
}
max = Math.max(max, lens[i]);
}
return max;
}
}
```

Python: BS, T: O(nlogn), S: O(n)

```class Solution(object):
def lengthOfLIS(self, nums):
LIS = []
def insert(target):
left, right = 0, len(LIS) - 1
# Find the first index "left" which satisfies LIS[left] >= target
while left <= right:
mid = left + (right - left) / 2
if LIS[mid] >= target:
right = mid - 1
else:
left = mid + 1
if left == len(LIS):
LIS.append(target);
else:
LIS[left] = target

for num in nums:
insert(num)

return len(LIS)
```

Python: DP, T: O(n^2), S: O(n)

```class Solution(object):
def lengthOfLIS(self, nums):
dp = []  # dp[i]: the length of LIS ends with nums[i]
for i in xrange(len(nums)):
dp.append(1)
for j in xrange(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp) if dp else 0
```

Python: wo

```class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
n = len(nums)
dp = [1] * n
max_len = 1
for i in xrange(n):
for j in xrange(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
max_len = max(max_len, dp[i])

return max_len 　　```

C++：DP

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

C++：BS

```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();
}
};　```

C++：BS

```class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = 0; i < nums.size(); ++i){

int lo = 0, hi = dp.size();
while (lo < hi){
int mi = (lo + hi)/2;
if (dp[mi] < nums[i]) lo = mi + 1;
else hi = mi;
}
if (hi == dp.size())
dp.push_back(nums[i]);
else dp[hi] = nums[i];
}
return dp.size();
}
};
```

[LeetCode] 673. Number of Longest Increasing Subsequence 最长递增序列的个数

[LeetCode] 674. Longest Continuous Increasing Subsequence 最长连续递增序列