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 is4. 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)