# Longest Increasing Subsequence

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(nlogn) time complexity?

## 题目大意：

给定一个未经排序的整数数组，寻找最长递增子序列的长度。

例如，

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

最长递增子序列是：`[2, 3, 7, 101]`，因而长度是`4`。注意可能存在不止一个LIS组合，只需要返回长度即可。

算法应该满足O(n^2)复杂度。

进一步思考：你可以将时间复杂度优化至O(*n\_log\_n*)吗？

## 解题思路：

### 1. **O(n^2)解法：**

动态规划（Dynamic Programming）

```
```

### 2. **O(n \* log n)解法**

下面我们来看一种优化时间复杂度到O(nlgn)的解法，这里用到了二分查找法，所以才能加快运行时间哇。思路是，我们先建立一个数组ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比ends数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比ends数组中的末尾元素还大的话，将此新元素添加到ends数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比ends数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个nums数组，此时ends数组的长度就是我们要求的LIS的长度，特别注意的是ends数组的值可能不是一个真实的LIS，比如若输入数组nums为{4, 2， 4， 5， 3， 7}，那么算完后的ends数组为{2， 3， 5， 7}，可以发现它不是一个原数组的LIS，只是长度相等而已，千万要注意这点

```
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        result = [nums[0]]
        for num in nums:
            if num < result[0]:
                result[0] = num
            elif num > result[len(result)-1]:
                result.append(num)
            else:
                start = 0 
                end = len(result)-1
                while start+1<end:
                    mid = (start+end)/2
                    if num > result[mid]:
                        start = mid
                    else:
                        end = mid
                if result[start]>=num:
                    result[start] = num
                else:
                    result[end] = num
        return len(result)
```