Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

The number of longest increasing subsequences

Before we do this, we can review the problem of LIS longest increasing subsequence.

1. LIS

The longest increasing subsequence

There are two approaches to the longest increasing subsequence: dynamic programming of O(n2) and greedy + dichotomy of O(nlogn).

1.1 Dynamic Planning

Dp [I] is defined as the length of the longest ascending subsequence ending with the ith element, where num[I] must be selected, then the state transition equation is (dp initialization value is 1) : dp[I] = Max (dp[j]) + 1; j < i, num[i] > num[j]

def findNumberOfLIS(nums) :
    dp = [1] * len(nums)
    for i in range(1.len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
Copy the code

Complexity analysis:

  • Time complexity: O(N2)
  • Space complexity: space with O(n) DP [n]

1.2 Greedy + binary search

We want the longest ascending subsequence, so we want to make sure that the ascending sequence is as slow as possible, so that the number added to the subsequence is as small as possible. Based on the above ideas, maintain an array D [I], representing the longest ascending subsequence of length I, and d[I] is the minimum value satisfying the ascending subsequence of length I. Use len to record the number of elements in array D, and the initial value D [0] = num[0].

Algorithm flow:

  • Traversal nums, when traversal nums[I] :
    • If nums[I] > d[len], add to the end of the array, len+1
    • Otherwise, find the first position in the D array greater than nums[I] and insert it
  • To sequence,2,5,3,7,101,18 [0]
    • Insert 0: d = [0]
    • Insert 2: d = [0,2]
    • D = [0,2,5]
    • D = [0,2,3]
    • D = [0,2,3,7]
    • D = [0,2,3,7,101]
    • The fourth step updates the end value of the oldest sequence with length 5: d = [0,2,3,7,18], and the longest increasing subsequence length is 5
def findNumberOfLIS(nums) :
    d = []
    for n in nums:
        if not d or n > d[-1]:
            d.append(n)
        else:
            left, right = 0.len(d) - 1
            while left < right:
                mid = left + (right - left) // 2
                if d[mid] < n:
                    left = mid + 1
                else:
                    right = mid
            d[left] = n
    return len(d)
Copy the code

Complexity analysis:

  • Time complexity: O(nlogn) uses binary lookup
  • Space complexity: O(n) d[n] aided space

2. The number of longest increasing subsequences

2.1 Dynamic Planning

Further solutions are made on the basis of LIS:

Dp [I] is defined as the length of the longest ascending subsequence ending with the ith element, and Freq [I] is defined as the number of the longest ascending subsequence ending with the ith element. If the length of nums is maxLen, then the answer is the sum of freq[I] for dp[I]=maxLen.

dp[i] = max(dp[j]) + 1; j < i, num[i] > num[j]

Freq [I] is the sum of freq[j] such that dp[I]=dp[j] + 1

def findNumberOfLIS(nums) :
    maxLen = 1
    freq = [1] * len(nums)
    dp = [1] * len(nums)
    for i in range(1.len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    freq[i] = freq[j]
                elif dp[j] + 1 == dp[i]:
                    freq[i] += freq[j]
        maxLen = max(maxLen, dp[i])
    sumFreq = 0
    for i in range(nums):
        if dp[i] == maxLen:
            sumFreq += freq[i]
    return sumFreq
Copy the code

Complexity analysis:

  • Time complexity: O(N2)
  • Space complexity: space with O(n) DP [n]