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;
}
}
Short Java solution using DP O(n log n)

Similar solution using ArrayList:
public int lengthOfLIS(int[] nums) { ArrayList<Integer> dp = new ArrayList<>(nums.length); for (int num : nums) { if (dp.size() == 0  dp.get(dp.size()1) < num) dp.add(num); else { int i = Collections.binarySearch(dp, num); dp.set((i<0) ? i1 : i, num); } } return dp.size(); }

The basic idea is present in the majority of solutions shared for this task, I have only tried to implement it in a manner as concise as possible without damaging the code readability.
The idea is that as you iterate the sequence, you keep track of the minimum value a subsequence of given length might end with, for all so far possible subsequence lengths. So dp[i] is the minimum value a subsequence of length i+1 might end with. Having this info, for each new number we iterate to, we can determine the longest subsequence where it can be appended using binary search. The final answer is the length of the longest subsequence we found so far.

Hello, it's really a nice answer. But I have a question, how did you come up the idea of using binary search. And what if we need to return the subsequence, will binary search still work? I tried to print the subsequence of your answer, the answer is not correct. But the length is correct. For example: [10, 9, 2, 5, 6，3, 7, 101, 18] ＝》 your code's answer: [2, 3, 6，7, 101]， But i think the right answer is [2, 5, 6，7, 101]. Thank you.

This is a great solution. By the way, what is the difference between two versions of Arrays.binarySearch()? If substitute it with another one, it has the error: java.lang.ArrayIndexOutOfBoundsException: 8 for input [10,9,2,5,3,7,101,18]... Has anyone seen where the problem is?
public class Solution { public int lengthOfLIS(int[] nums) { // keep track of the end elements of each lists int[] dp = new int[nums.length]; int len = 0; for(int i = 0; i<nums.length; i++){ int pos = Arrays.binarySearch(dp,nums[i]); if(pos < 0){ pos =  pos  1; } dp[pos] = nums[i]; if(pos == len) len++; } return len; } }

Arrays.binarySearch()
returns(  insertion_index  1)
in cases where the element was not found in the array. Initially thedp
array is all zeroes. For all zeroes array the insertion index for any element greater than zero is equal to the length of the array (dp.length
in this case). This means that the number needs to be added to the end of the array to keep the array sorted.As a result
pos
is equal toinsertion_index
, which is equal todp.length
. So thedp[pos] = nums[i];
line fails, becausepos
is out of bounds.This problem does not happen when searching just part of the array by using
Arrays.binarySearch(dp, 0, len, nums[i])
, because in this case the insertion index islen
.By the way the issue will happen on any input that contains a positive integer, e.g. [1].

@julielong That's because dp[] is not storing the sequence as explained by the author in the reply. dp[i] is storing the smallest number such that the length is i+1.

Where did you find the definition? According to Java API (https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(char[], int, int, char) It is defined as “index of the search key, if it is contained in the array within the specified range; otherwise, ((insertion point)  1)”

How is this solution better if your ArrayList's backed array has the same length as the original array (nums.length). That means you don't save any space using the dynamic array, but also the solution is heavier due to higher level data structure. You don't have to initialize your ArrayList with nums.length  then it will make sense.