In fact, this is a variant of the **insert sort** algorithm, we use **binary search** to find the insert point.

The **dp** array is used to store the elements of the **Longest Increasing Subsequence**, of course, you can also use **ArrayList** to do the same job.

```
public int lengthOfLIS(int[] nums) {
/**
* dp is used to store the elements of the Longest Increasing Subsequence
*/
int[] dp = new int[nums.length];
/**
* initial length of the LIS
*/
int len = 0;
for (int num : nums) {
/**
* search in a bounded array dp[0..len) to find the index of the
* insert point for the current num
*/
int idx = Arrays.binarySearch(dp, 0, len, num);
/**
* if the element is not in the bounded array dp[0..len), then
* we get the index of the insert point using a conversion.
*/
if (idx < 0) {
idx = -idx - 1;
}
/**
* update the element
*/
dp[idx] = num;
/**
* if the updated element is the last element, then the length of
* the LIS may be updated or not, but it is always equal to idx+1
*/
if (idx == len) {
len = idx + 1;
}
}
return len;
}
```