I saw this solution here a long time ago, for me it's really hard to think of it :)

```
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int n = nums.length, len = 1;
int[] tailTable = new int[n];
tailTable[0] = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] < tailTable[0]) {
// new smallest value
tailTable[0] = nums[i];
} else if (nums[i] > tailTable[len - 1]) {
// nums[i] wants to extend largest subsequence
tailTable[len++] = nums[i];
} else {
// nums[i] wants to be current end candidate of an existing subsequence
// It will replace ceil value in tailTable
tailTable[ceilIndex(tailTable, -1, len - 1, nums[i])] = nums[i];
}
}
return len;
}
// binary search helper
int ceilIndex(int[] tailTable, int lo, int hi, int key) {
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (tailTable[mid] >= key) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
}
```