Skip to main content

Number of Longest Increasing Subsequence

Question​

None

Example 1
Input: [10, 9, 2, 5, 3, 7, 101, 18] 

Output: 3 (The longest increasing subsequence is [2, 3, 7, 101], therefore the result is 3)

Solution​

all//Number of Longest Increasing Subsequence.py


def longest_increasing_subsequence(nums):
    n = len(nums)
    lis = [1]*n
    count = [1]*n

    for i in range (1 , n):
        for j in range(0 , i):
            if nums[i] > nums[j] and lis[i]< lis[j] + 1 :
                lis[i] = lis[j]+1
                count[i] = count[j]

            elif nums[i] == nums[j] and lis[i] == lis[j]:
                count[i] = count[i]+count[j]

    maximum = 0
    result = 0
    for i in range(n):
        if maximum < lis[i]:
            maximum = lis[i]
            result = count[i]

        elif maximum == lis[i]:
            result += count[i]

    return result

# Driver program to test above
nums = [1,3,5,4,7]
print(longest_increasing_subsequence(nums))