Sponsored
Sponsored
This approach utilizes two arrays to track the length of the longest increasing subsequence ending at each index and the count of such subsequences. The first array, lengths, will store the length of L.I.S. ending at each position, and the second array, counts, will store how many times such a subsequence appears. We iterate through each possible pair of indices to update these arrays accordingly.
Time Complexity: O(n^2) where n is the number of elements in the input array.
Space Complexity: O(n) used for the lengths and counts arrays.
1def findNumberOfLIS(nums):
2 n = len(nums)
3 if n <= 0:
4 return 0
5
6 lengths = [1] * n
7 counts = [1] * n
8
9 max_len, result = 0, 0
10
11 for i in range(n):
12 for j in range(i):
13 if nums[i] > nums[j]:
14 if lengths[j] + 1 > lengths[i]:
15 lengths[i] = lengths[j] + 1
16 counts[i] = counts[j]
17 elif lengths[j] + 1 == lengths[i]:
18 counts[i] += counts[j]
19
20 if lengths[i] > max_len:
21 max_len = lengths[i]
22 result = counts[i]
23 elif lengths[i] == max_len:
24 result += counts[i]
25
26 return result
27
28print(findNumberOfLIS([1, 3, 5, 4, 7]))The Python solution relies on dynamic typing and constructs like list comprehensions to streamline the initialization of lengths and counts. The nested iteration pairs remain straightforward and easily track state within the constraints.