Count Longest Increasing Subsequences

Problem

Return the number of longest strictly increasing subsequences of arr, counted by index choices.

Track lengths[i] and counts[i] for subsequences ending at each index, adding counts[j] to counts[i] whenever j extends the same best length. Equal values do not extend each other, and an empty list gives 0.

Hint

When a new predecessor ties the best length, inherit its count instead of resetting.

Test cases

case 1

in: [[1,3,5,4,7]]

expected: 2

case 2

in: [[2,2,2,2,2]]

expected: 5

case 3

in: [[1,2,3]]

expected: 1

case 4

in: [[]]

expected: 0

case 5

in: [[1,1,2,2,3,3]]

expected: 8

Starter codePython

def count_lis(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor