#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/number-of-lis-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/number-of-lis-implementation

Repovive

LeetCode 673 Number of Longest Increasing Subsequences - Implementation - Longest Increasing Subsequence | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 673 Number of Longest Increasing Subsequences - Implementation

The code

Here's the full solution:

function findNumberOfLIS(nums)
    n := length of nums
    length := array of size n, all 1
    count := array of size n, all 1
    for i from 1 to n - 1
        for j from 0 to i - 1
            if nums[j] < nums[i]
                if length[j] + 1 > length[i]
                    length[i] := length[j] + 1
                    count[i] := count[j]
                else if length[j] + 1 = length[i]
                    count[i] := count[i] + count[j]
    maxLen := max of length array
    result := 0
    for i from 0 to n - 1
        if length[i] = maxLen
            result := result + count[i]
    return result

Time: $O(n^2)$ . Space: $O(n)$ .

You track both the length and count of LIS ending at each position. When you find a longer subsequence, reset the count. When you find an equal-length one, add to the count.