LeetCode 300. Longest ascending subsequence

Title Description:

Dynamic Planning Edition
Time complexity: O(n2)
Spatial complexity: O(n)

Python code:

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)

Binary Search Edition

Time complexity: O(nlogn). Binary search takes logn time and calls n times.
Spatial complexity: O(n), using list cell s of size n.

Create a new array cell to hold the longest ascending subsequence. The original sequence is traversed and each element is dichotomized into the cell. If all the elements in a cell are smaller than it, insert it to the end. Otherwise, use it to cover the smallest of the larger elements.
In short, the idea is to store smaller elements in a cell. In this way, the cell may not be the real longest ascending subsequence, but the length is correct.

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)

Use bisect module binary lookup:

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 module

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

>>> 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

The bisect function is an alias for the bisect_right function. The index returned is the position after the original sequence of equal elements, and the new elements are inserted to the right of the old elements.
The index returned by the bisect_left function is the position of the equivalent element in the original sequence, and the new element is inserted to the left of the old element.

LeetCode 673. Number of longest incremental subsequences

Title Description:

Python code:

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())