## 题目描述：

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(n^2) complexity.

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

## 解题思路：

O(n^2)解法（运行时间1676ms）

`dp[x] = max(dp[x], dp[y] + 1) 其中 y < x 并且 nums[x] > nums[y]`

## Python代码：

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

O(n * log n)解法（运行时间44ms）

## Python代码：

``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
dp = []
for x in range(size):
low, high = 0, len(dp) - 1
while low <= high:
mid = (low + high) / 2
if dp[mid] >= nums[x]:
high = mid - 1
else:
low = mid + 1
if low >= len(dp):
dp.append(nums[x])
else:
dp[low] = nums[x]
return len(dp)
``````

Pingbacks已关闭。