# 300. 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(n^2) complexity.

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

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

Thoughts

1. O(n^2) solution with recursive and dynamic programming approach by GeeksforGeeks

2. Dynamic Programming (Original GeeksforGeeks explanation) O(n^2)

3. Binary search + Dynamic Programming: O(nlogn) (Original GeeksforGeeks explanation)

Code Binary Search (Java) inspired by GeeksforGeeks: “end element of smaller list is smaller than end elements of larger lists“.

``````record the tail table by keeping updating current value to correct position into the tail table
through binary search
``````
``````class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (i + j) / 2;
if (tails[m] < x)
i = m + 1;
else
j = m;
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
}
``````

using Arrays.binarySearch by jopiko123:

``````public class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;

for(int x : nums) {
int i = Arrays.binarySearch(dp, 0, len, x);
if(i < 0) i = -(i + 1);
dp[i] = x;
if(i == len) len++;
}

return len;
}
}
``````

Code Binary Search with O(nlogn) by dtccwl, inspired by GeeksforGeeks

``````class Solution {
public:
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();
}
};
``````