【Day 56 】2024-06-02 - 673. 最长递增子序列的个数

[azl397985856]

673. 最长递增子序列的个数

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/

前置知识

• 动态规划

  题目描述

  
  给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 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。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

[xy147]

js代码

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; // 重置计数
                } else if (dp[j] + 1 === dp[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i]; // 重置计数
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

复杂度分析

时间复杂度：O(n2) 空间复杂度：O(n)

[Dtjk]

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: n = len(nums) f = [1] n cnt = [1] n longest = 1 for i in range(1, n): for j in range(i): if nums[j] < nums[i]: cur = f[j] + 1 if cur > f[i]: f[i] = cur cnt[i] = cnt[j] elif cur == f[i]: cnt[i] += cnt[j] longest = max(longest, f[i])

#    #  print(longest)
#     print(cnt)
#     print(f)
    ans = 0
    for i in range(n):
        if f[i] == longest:
            ans += cnt[i]

    return ans

[pandapls]

var findNumberOfLIS = function(nums) {
    if (!nums || nums.length === 0) {
        return 0
    }

    let dp = Array.from({length: nums.length}).fill(1)
    let counts = Array.from({length: nums.length}).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    counts[i] = counts[j];
                } else if (dp[j] + 1 === dp[i]) {
                    counts[i] += counts[j];
                }
            }
        }
    }
    let maxLen = Math.max(...dp);
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (dp[i] === maxLen) {
            count += counts[i];
        }
    }

    return count;
};

复杂度分析

• 时间复杂度：O(n的平凡)
• 空间复杂度：O(n)