动态规划之——最长上升子序列

LeetCode300. 最长上升子序列

题目描述：

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

---

动态规划版
时间复杂度：O(n2)
空间复杂度：O(n)

Python代码：

class Solution:
    def lengthOfLIS(self, nums):
        if nums == []:
            return 0
        cell = [1]*len(nums)
        for i in range(1,len(nums)):
            for j in range(i):
                if(nums[j] < nums[i]):
                    cell[i] = max(cell[i], cell[j]+1)
        return max(cell)

二分查找版

时间复杂度：O(nlogn)。二分搜索需要花费logn的时间且调用n次。
空间复杂度：O(n)，用了大小为 n的列表cell。

新建数组 cell，用于保存最长上升子序列。对原序列进行遍历，将每位元素二分插入 cell 中。如果 cell 中元素都比它小，将它插到最后。否则，用它覆盖掉比它大的元素中最小的那个。
总之，思想就是让 cell 中存储比较小的元素。这样，cell 未必是真实的最长上升子序列，但长度是对的。

class Solution:
    def lengthOfLIS(self, nums):
        size = len(nums)
        if size<2:
            return size
        
        cell = [nums[0]]
        for num in nums[1:]:
            if num>cell[-1]:
                cell.append(num)
                continue
            
            l,r = 0,len(cell)-1
            while l<r:
                mid = l + (r - l) // 2
                if cell[mid]<num:
                    l = mid + 1
                else:
                    r = mid
            cell[l] = num
        return len(cell)

使用bisect模块二分查找：

class Solution:
    def lengthOfLIS(self, nums):
        cell = [-float('inf')]
        for i in nums:
            if i > cell[-1]:
                cell += [i]
            else:
                cell[bisect.bisect_left(cell, i)] = i
        return len(cell) - 1

---

bisect模块

bisect.bisect(seq, item, lo = 0, hi =len(list_name))

在有序列表seq中查找item的位置，并且返回其索引index，使得
插入item后序列依然保持有序。
有两个可选参数lo和hi来缩小搜索范围，lo的默认值为0，hi的默
认值为序列的长度。

>>> import bisect
>>> a = [3,4,6,7,9]
>>> b = bisect.bisect(a,8)
>>> b
4
>>> b = bisect.bisect(a,9.0)
>>> b
5
>>> b = bisect.bisect_left(a,9.0)
>>> b
4

bisect函数是bisect_right函数的别名，返回的索引是原序列相等元素之后的位置，新元素插入在旧元素的右边。
bisect_left函数返回的索引是原序列中相等元素的位置，新元素插入在旧元素的左边。

---

LeetCode673. 最长递增子序列的个数

题目描述：

给定一个未排序的整数数组，找到最长递增子序列的个数。
示例:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

Python代码：

class Solution:
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        l = len(nums)
        dq = list()
        totals = list()
        for num in nums:
            index = len(dq)-1
            if not dq or num >dq[-1]:
                dq.append(num)
                totals.append(collections.defaultdict(int))
            else:
                while index >= 0 and dq[index]>= num:
                    index -= 1
                dq[index+1] = num
            if not index+1:
                totals[index+1][num] +=1
            else:
                totals[index+1][num] += sum([val for key,val in totals[index].items() if key <num ])
        return sum(totals[-1].values())