23.07.21 Today’s Leetcode

673. Number of Longest Increasing Subsequence (medium)

TLE at 34/223

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        p = 0

        def dfs(index, prev, length):
            nonlocal res, p
            if length > p:
                res = 1
                p = length
            elif length == p:
                res += 1

            for i in range(index, n):
                value = nums[i]
                if value > prev:
                    dfs(i + 1, value, length + 1)

        dfs(0, -math.inf, 0)
        return res

Same..

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        def dfs(index, prev, length):
            temp = 1
            size = length
            for i in range(index, n):
                value = nums[i]
                if value <= prev: continue
                a, b = dfs(i + 1, value, length + 1)
                if a > size:
                    temp = b
                elif a == size:
                    temp += b
                size = max(size, a)
                    
            return (size, temp)

        p = dfs(0, -math.inf, 0)
        # print(p)
        return p[1]

DP Solution.

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n

        lengths = [1] * n
        counts = [1] * n

        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if lengths[j] + 1 > lengths[i]:
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
                    elif lengths[j] + 1 == lengths[i]:
                        counts[i] += counts[j]

        max_length = max(lengths)
        return sum(count for length, count in zip(lengths, counts) if length == max_length)