## Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given `[10, 9, 2, 5, 3, 7, 101, 18]`

,

The longest increasing subsequence is `[2, 3, 7, 101]`

, therefore the length is `4`

. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(*n2*) complexity.

Follow up: Could you improve it to O(*n* log *n*) time complexity?

## Analysis

- 遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数
- tail 表示当前valid数组的最后一个数，
- 对于当前读到的数x
- 如果x>tail，则把x append到数组中
- 如果x<valid数组的第一个数，则将其替换为x
- 否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x

- 返回valid数组中有效的数个数

时间复杂度: O(nlogn)

## Code

Reference

[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

[2] https://leetcode.com/problems/longest-increasing-subsequence/