673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Solution

Approach 1: the number of LIS consists of 2 parts -- the sequences that ends with the same item, and sequences that ends with different items.

Code (Python)

Approach 1:

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums:
            return 0

        # longest subsequence ending with nums[i]
        longest = [1 for _ in range(len(nums))]
        # number of longest subsequences ending with nums[i]
        num_longest = [1 for _ in range(len(nums))]
        # global length of LIS
        global_max_length = 1
        # global number of LIS
        global_num_max_length = 1

        for i in range(1, len(nums)):

            for j in range(i):
                if nums[j] >= nums[i]:
                    continue
                if longest[j] + 1 == longest[i]:
                    num_longest[i] += num_longest[j]
                elif longest[j] + 1 > longest[i]:
                    longest[i] = longest[j] + 1
                    num_longest[i] = num_longest[j]

            if global_max_length == longest[i]:
                global_num_max_length += num_longest[i]
            elif global_max_length < longest[i]:
                global_max_length = longest[i]
                global_num_max_length = num_longest[i]
        return global_num_max_length

Code (C++)

Approach 1:

Approach 2: