Appearance
673. 最长递增子序列的个数
题目描述
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
提示:
- `1 <= nums.length <= 2000`
-106 <= nums[i] <= 106
难度： Medium
题解代码
javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findNumberOfLIS = function(nums) {
const len = nums.length
let maxLen = 1
let res = 1
const dp = Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
// maxLen = Math.max(dp[i], maxLen)
if (maxLen === dp[i]) {
res += 1
} else if (maxLen < dp[i]) {
res = 1
maxLen = dp[i]
}
}
return res
};