LIS

教材经典DP，O(n^2)的算法可以明显看出来就是序列型DP

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [0] * (n + 1)

        for i in xrange(1, n + 1):
            dp[i] = 1
            for j in xrange(1, i):
                if nums[j - 1] < nums[i - 1]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

这题还有一个隐藏的个人觉得并不算DP的O(nlgn)的做法，它通过维护一个保持递增的DP序列，同时每次对新元素进行二分搜索找到它在dp序列上的位置并将对应位置改为当前元素来找到这个最长dp序列，最后的dp序列不一定是真正的最长LIS但肯定长度和最长的LIS长度一样（这一点也是不太好弄懂的地方）

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = []

        for num in nums:
            index = bisect.bisect_left(dp, num)
            if index >= len(dp):
                dp.append(num)
            else:
                dp[index] = num

        return len(dp)