HackMD
673. Number of Longest Increasing Subsequence
題目描述
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
範例
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
Constraints:
- 1 <=
nums.length<= 2000 - -106 <=
nums[i]<= 106
解答
Python
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
N = len(nums)
d = [1] * N
c = [1] * N
for j in range(1, N):
for i in range(j):
if nums[i] < nums[j]:
if d[i] + 1 > d[j]:
d[j] = d[i] + 1
c[j] = c[i]
elif d[i] + 1 == d[j]:
c[j] += c[i]
L = max(d)
return sum(c[i] for i in range(N) if d[i] == L)
Yen-Chi ChenFri, Jul 21, 2023
