Medium

题目描述

给定一个整数数组 nums，返回最长递增子序列的个数。

注意子序列必须是严格递增的。

示例 1:

输入: nums = [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和 [1, 3, 5, 7]。

示例 2:

输入: nums = [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是 1，长度为 1 的递增子序列有 5 个，因此输出 5。

提示:

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6
  • 答案保证在 32 位整数范围内。

解题思路

这道题是经典的最长递增子序列（LIS）问题的变形，不仅要求最长长度，还要统计满足条件的子序列个数。

解题思路： 使用动态规划来解决。我们需要维护两个数组：

  1. dp[i]：表示以 nums[i] 结尾的最长递增子序列的长度
  2. count[i]：表示以 nums[i] 结尾的最长递增子序列的个数

状态转移：

  • 对于每个位置 i，我们遍历前面所有位置 j（j < i）
  • 如果 nums[j] < nums[i]，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面
  • 如果 dp[j] + 1 > dp[i]，说明找到了更长的递增子序列，更新 dp[i] 和 count[i]
  • 如果 dp[j] + 1 == dp[i]，说明找到了另一种达到相同最长长度的方案，累加 count[i]

算法步骤：

  1. 初始化所有 dp[i] = 1，count[i] = 1（每个元素本身构成长度为1的子序列）
  2. 双重循环进行状态转移
  3. 找出全局最长长度 maxLen
  4. 累加所有 dp[i] == maxLen 对应的 count[i]

代码实现

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);     // dp[i]: 以nums[i]结尾的最长递增子序列长度
        vector<int> count(n, 1);  // count[i]: 以nums[i]结尾的最长递增子序列个数
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        
        int maxLen = *max_element(dp.begin(), dp.end());
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                result += count[i];
            }
        }
        
        return result;
    }
};

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        
        dp = [1] * n      # dp[i]: 以nums[i]结尾的最长递增子序列长度
        count = [1] * n   # count[i]: 以nums[i]结尾的最长递增子序列个数
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
        
        max_len = max(dp)
        result = 0
        for i in range(n):
            if dp[i] == max_len:
                result += count[i]
        
        return result

public class Solution {
    public int FindNumberOfLIS(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        
        int[] dp = new int[n];     // dp[i]: 以nums[i]结尾的最长递增子序列长度
        int[] count = new int[n];  // count[i]: 以nums[i]结尾的最长递增子序列个数
        
        // 初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            count[i] = 1;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        
        int maxLen = dp.Max();
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                result += count[i];
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    
    const lengths = new Array(n).fill(1);
    const counts = new Array(n).fill(1);
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                } else if (lengths[j] + 1 === lengths[i]) {
                    counts[i] += counts[j];
                }
            }
        }
    }
    
    const maxLength = Math.max(...lengths);
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        if (lengths[i] === maxLength) {
            result += counts[i];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)双重循环遍历数组进行状态转移
空间复杂度O(n)使用两个长度为 n 的数组存储 dp 和 count 信息

相关题目