最长递增子序列的变种：最长递增子序列的个数（进阶版——允许重复元素）
字数 1579 2025-11-03 12:22:39
最长递增子序列的变种：最长递增子序列的个数（进阶版——允许重复元素）
题目描述：
给定一个整数数组 nums，其中可能包含重复元素。请计算最长递增子序列（LIS）的个数。注意：如果最长递增子序列有多个，你需要统计所有不同的最长递增子序列的数量。这里的"不同"指的是子序列的元素组成不同（考虑元素在数组中的索引位置），即使元素值相同但来自不同位置也被视为不同的子序列。
解题过程：
- 问题理解：
- 我们需要找到数组中最长的严格递增子序列，并统计这样的子序列有多少个
- 由于存在重复元素，我们需要考虑子序列中元素的索引位置
- 例如：nums = [1,3,5,4,7]
- 最长递增子序列有：[1,3,4,7]、[1,3,5,7]等
- 长度为4，需要统计所有长度为4的递增子序列
- 动态规划状态定义：
- 定义两个数组：
- lengths[i]：以nums[i]结尾的最长递增子序列的长度
- counts[i]：以nums[i]结尾的最长递增子序列的个数
- 状态转移方程：
- 对于每个位置i，我们需要检查所有j < i：
- 如果nums[j] < nums[i]：
- 如果lengths[j] + 1 > lengths[i]：
- 更新lengths[i] = lengths[j] + 1
- 重置counts[i] = counts[j]
- 如果lengths[j] + 1 == lengths[i]：
- counts[i] += counts[j]
- 如果lengths[j] + 1 > lengths[i]：
- 处理重复元素的特殊情况：
- 当存在重复元素时，我们需要避免重复计数
- 如果j < i且nums[j] == nums[i]：
- 如果lengths[j] == lengths[i]：
- 说明这两个位置可以形成相同的递增子序列
- 我们需要用counts[j]替换counts[i]来避免重复
- 如果lengths[j] == lengths[i]：
- 算法步骤：
- 初始化lengths数组全为1，counts数组全为1
- 遍历i从0到n-1：
- 遍历j从0到i-1：
- 如果nums[j] < nums[i]：
- 如果lengths[j] + 1 > lengths[i]：
- lengths[i] = lengths[j] + 1
- counts[i] = counts[j]
- 否则如果lengths[j] + 1 == lengths[i]：
- counts[i] += counts[j]
- 如果lengths[j] + 1 > lengths[i]：
- 否则如果nums[j] == nums[i]：
- 如果lengths[j] == lengths[i]：
- counts[i] = counts[j] // 避免重复计数
- 如果lengths[j] > lengths[i]：
- lengths[i] = lengths[j]
- counts[i] = counts[j]
- 如果lengths[j] == lengths[i]：
- 如果nums[j] < nums[i]：
- 遍历j从0到i-1：
- 统计最终结果：
- 找到最长递增子序列的长度max_len
- 遍历所有位置i，如果lengths[i] == max_len，将counts[i]累加
- 复杂度分析：
- 时间复杂度：O(n²)
- 空间复杂度：O(n)
示例演示：
nums = [1,3,5,4,7]
执行过程：
- i=0: lengths[0]=1, counts[0]=1
- i=1: 找到j=0(nums[0]=1<3), lengths[1]=2, counts[1]=1
- i=2: 找到j=0,1, lengths[2]=3, counts[2]=1
- i=3: 找到j=0,1, lengths[3]=3, counts[3]=1
- i=4: 找到j=0,1,2,3, lengths[4]=4, counts[4]=2
最终结果：最长长度为4，有2个这样的子序列