~Why it's a DP problem?~

dp[i] holds the smallest number tan have LIS with length i+1.

```
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length < 1) return 0;
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
// if not found, return -(termination index + 1),
// where you should insert the number.
if (i < 0) {
i = -(i + 1);
dp[i] = num;
if (i == len) len++;
}
// if found, do nothing.
}
return len;
}
```

p.s: I do hate people using titles such as easy explanation!!!!!, best submission, best solution. That's why I use Super Brief to satirize on them. LoL.