O(N^2)

```
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0: return 0
dp = [1]*n
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if nums[j] > nums[i]:
dp[i] = max(dp[i], 1+dp[j])
return max(dp)
```

O(NlogN)

```
from bisect import bisect_left
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
n = len(nums)
if n == 0: return ans
dp = [0]*n # minimal val for length i+1
for x in nums:
j = bisect_left(dp[:ans], x)
dp[j] = x
if j == ans: ans += 1
return ans
```