This solution uses Binary Search + DP

```
1, traverse from 0 to len-1, the DP array keep the longest sequence.
2, if the val is bigger than largest in the dp array, add it to the end;
3, if it is among the sequence, return the pos that bigger than pres, update the array with this position if val is smaller than dp[pos];
This is to keep the sequence element with the smallest number.
```

For example:

```
10, 9, 2, 5, 3, 7, 101, 18
10
9
2
2,5
2,3
2,3,7
2,3,7,101
2,3,7,18
```

The follow is the solution:

```
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int len = 0;
for (int i = 1; i < nums.length; i++) {
int pos = binarySearch(dp,len,nums[i]);
if (nums[i] < dp[pos]) dp[pos] = nums[i];
if (pos > len) {
len = pos;
dp[len] = nums[i];
}
}
return len+1;
}
private int binarySearch(int[] dp, int len, int val) {
int left = 0;
int right = len;
while(left+1 < right) {
int mid = left + (right-left)/2;
if (dp[mid] == val) {
return mid;
} else {
if (dp[mid] < val) {
left = mid;
} else {
right = mid;
}
}
}
if (dp[right] < val) return len+1;
else if (dp[left] >= val) return left;
else return right;
}
}
```