`O(n^2)`

solution uses DP. Assume `dp[i]`

is the `LIS`

that ends up with `nums[i]`

, then `dp[i] = max(dp[0..i-1]) + 1`

.

```
class Solution(object):
def lengthOfLIS(self, nums):
dp = [1] * len(nums)
for i in xrange(1, len(nums)):
dp[i] = max([
dp[j] for j in xrange(i - 1, -1, -1) if nums[i] > nums[j]
] or [0]) + 1
return max(dp or [0])
```

`O(nlog(n))`

solution uses binary search. We maintain an increasing array making itself as long and its elements as small as possible.

```
class Solution(object):
def lengthOfLIS(self, nums):
lis = []
for num in nums:
i = bisect.bisect_left(lis, num)
if i >= len(lis):
lis.append(num)
else:
lis[i] = num
return len(lis)
```