```
public class Solution {
public int lengthOfLIS(int[] a) {
int n = a.length;
int[] tail = new int[n];
int[] prev = new int[n];
int len = 0;
for (int i = 0; i < n; i++) {
int pos = lower_bound(a, tail, len, a[i]);
if (pos == len) {
++len;
}
prev[i] = pos > 0 ? tail[pos - 1] : -1;
tail[pos] = i;
}
return len;
}
int lower_bound(int[] a, int[] tail, int len, int key) {
int lo = -1;
int hi = len;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (a[tail[mid]] < key) {
lo = mid;
} else {
hi = mid;
}
}
return hi;
}
}
```