Maybe this is faster is because I use a tricky binary search.

```
public class Solution
{
public int lengthOfLIS(int[] nums)
{
if(nums.length == 0) return 0;
int[] tails = new int[nums.length];
int max = 0;
tails[max] = Integer.MAX_VALUE;
for(int i = 0; i< nums.length;i++)
{
if(nums[i] <= tails[0]) tails[0] = nums[i];
else if(nums[i] >= tails[max]) tails[++max] = nums[i];
else
{
tails[binarySearch(0,max,tails,nums[i])] = nums[i];
}
}
return max+1;
}
public int binarySearch(int L, int R, int[] tails, int target)
{
while(L <= R)
{
int M = L + (R - L)/2;
if(target > tails[M]) L = M + 1;
else R = M - 1;
}
return L;
}
}
```

I won't talk about Patience Sort because there are so many documents about it.

For this Binary Search:

If the target value is in the array, it returns index of the target value.

If the target value is not in the array, it returns the index of where it should be. That is just the tail index that we need.