# The Longest Rising Subsequence of Dynamic Programming

###### LeetCode 300. Longest ascending subsequence

Title Description:

Given an unordered array of integers, find the length of the longest ascending subsequence.
Example:
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Interpretation: The longest ascending subsequence is [2,3,7,101], and its length is 4.

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

Find the location of item in the sequential table seq and return its index so that
After inserting item, the sequence remains in order.
There are two optional parameters lo and hi to narrow the search range. The default value of Lo is 0 and the silence of hi is 0.
The recognition value is the length of the sequence.

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

Given an unsorted array of integers, find the number of the longest incremental subsequences.
Example:
Input: [1, 3, 5, 4, 7]
Output: 2
Interpretation: There are two longest incremental subsequences, namely [1, 3, 4, 7] and [1, 3, 5, 7].

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

Keywords: Python

Added by idweb on Sat, 05 Oct 2019 12:58:43 +0300