最长递增子序列的变种：最长递增子序列的长度与具体序列（允许重复元素）
我将为您讲解一个关于最长递增子序列的变种问题。这个问题不仅要求找到最长递增子序列的长度，还需要找出具体的序列内容，并且允许序列中存在重复元素。
问题描述
给定一个整数数组nums，找到其中最长的严格递增子序列，并返回这个子序列本身。如果有多个最长递增子序列，返回任意一个即可。
注意：子序列不要求连续，但必须是严格递增的（允许重复元素，但子序列中不能有重复）。
示例
输入：nums = [10,9,2,5,3,7,101,18]
输出：[2,3,7,101] 或 [2,5,7,101] 等
解释：最长递增子序列的长度是4，可能有多个解。
解题过程
步骤1：理解问题本质
我们需要找到数组中最长的严格递增子序列。与基础的最长递增子序列问题不同，这里我们需要记录具体的序列内容，而不仅仅是长度。
步骤2：定义状态
我们使用动态规划来解决这个问题：
- dp[i]：表示以第i个元素结尾的最长递增子序列的长度
- prev[i]：记录在以第i个元素结尾的最长递增子序列中，i的前一个元素的索引
步骤3：状态转移方程
对于每个位置i，我们需要检查所有j < i：
如果 nums[j] < nums[i] 且 dp[j] + 1 > dp[i]，则：
dp[i] = dp[j] + 1
prev[i] = j
步骤4：初始化
- 每个位置初始的最长递增子序列长度至少为1（只包含自身）
- prev数组初始化为-1，表示没有前驱元素
步骤5：算法实现
让我们通过示例详细演示：
输入：nums = [10,9,2,5,3,7,101,18]
步骤5.1：初始化
i=0: dp[0]=1, prev[0]=-1
i=1: dp[1]=1, prev[1]=-1
i=2: dp[2]=1, prev[2]=-1
i=3: dp[3]=1, prev[3]=-1
i=4: dp[4]=1, prev[4]=-1
i=5: dp[5]=1, prev[5]=-1
i=6: dp[6]=1, prev[6]=-1
i=7: dp[7]=1, prev[7]=-1
步骤5.2：逐步计算
i=0: 没有j<0，保持初始状态 [1,-1]
i=1: j=0, nums[0]=10 > nums[1]=9，不满足递增
结果：[1,-1], [1,-1]
i=2: j=0, nums[0]=10 > nums[2]=2，不满足
j=1, nums[1]=9 > nums[2]=2，不满足
结果：[1,-1], [1,-1], [1,-1]
i=3: j=0, nums[0]=10 > nums[3]=5，不满足
j=1, nums[1]=9 > nums[3]=5，不满足
j=2, nums[2]=2 < nums[3]=5，满足条件
dp[3] = max(dp[3], dp[2]+1) = max(1, 1+1) = 2
prev[3] = 2
结果：[1,-1], [1,-1], [1,-1], [2,2]
i=4: j=0, nums[0]=10 > nums[4]=3，不满足
j=1, nums[1]=9 > nums[4]=3，不满足
j=2, nums[2]=2 < nums[4]=3，满足条件
dp[4] = max(dp[4], dp[2]+1) = max(1, 1+1) = 2
prev[4] = 2
j=3, nums[3]=5 > nums[4]=3，不满足
结果：[1,-1], [1,-1], [1,-1], [2,2], [2,2]
i=5: j=0, nums[0]=10 > nums[5]=7，不满足
j=1, nums[1]=9 > nums[5]=7，不满足
j=2, nums[2]=2 < nums[5]=7，满足条件
dp[5] = max(dp[5], dp[2]+1) = max(1, 1+1) = 2
prev[5] = 2
j=3, nums[3]=5 < nums[5]=7，满足条件
dp[5] = max(2, dp[3]+1) = max(2, 2+1) = 3
prev[5] = 3
j=4, nums[4]=3 < nums[5]=7，满足条件
dp[5] = max(3, dp[4]+1) = max(3, 2+1) = 3
保持prev[5]=3
结果：[1,-1], [1,-1], [1,-1], [2,2], [2,2], [3,3]
i=6: j=0, nums[0]=10 < nums[6]=101，满足条件
dp[6] = max(dp[6], dp[0]+1) = max(1, 1+1) = 2
prev[6] = 0
j=1, nums[1]=9 < nums[6]=101，满足条件
dp[6] = max(2, dp[1]+1) = max(2, 1+1) = 2
保持prev[6]=0
j=2, nums[2]=2 < nums[6]=101，满足条件
dp[6] = max(2, dp[2]+1) = max(2, 1+1) = 2
保持prev[6]=0
j=3, nums[3]=5 < nums[6]=101，满足条件
dp[6] = max(2, dp[3]+1) = max(2, 2+1) = 3
prev[6] = 3
j=4, nums[4]=3 < nums[6]=101，满足条件
dp[6] = max(3, dp[4]+1) = max(3, 2+1) = 3
保持prev[6]=3
j=5, nums[5]=7 < nums[6]=101，满足条件
dp[6] = max(3, dp[5]+1) = max(3, 3+1) = 4
prev[6] = 5
结果：[1,-1], [1,-1], [1,-1], [2,2], [2,2], [3,3], [4,5]
i=7: j=0, nums[0]=10 < nums[7]=18，满足条件
dp[7] = max(dp[7], dp[0]+1) = max(1, 1+1) = 2
prev[7] = 0
j=1, nums[1]=9 < nums[7]=18，满足条件
dp[7] = max(2, dp[1]+1) = max(2, 1+1) = 2
保持prev[7]=0
j=2, nums[2]=2 < nums[7]=18，满足条件
dp[7] = max(2, dp[2]+1) = max(2, 1+1) = 2
保持prev[7]=0
j=3, nums[3]=5 < nums[7]=18，满足条件
dp[7] = max(2, dp[3]+1) = max(2, 2+1) = 3
prev[7] = 3
j=4, nums[4]=3 < nums[7]=18，满足条件
dp[7] = max(3, dp[4]+1) = max(3, 2+1) = 3
保持prev[7]=3
j=5, nums[5]=7 < nums[7]=18，满足条件
dp[7] = max(3, dp[5]+1) = max(3, 3+1) = 4
prev[7] = 5
j=6, nums[6]=101 > nums[7]=18，不满足
结果：[1,-1], [1,-1], [1,-1], [2,2], [2,2], [3,3], [4,5], [4,5]
步骤6：构造结果
最终dp数组：[1,1,1,2,2,3,4,4]
最长长度为4，对应的结束位置是索引6
从索引6开始回溯：
6 → prev[6]=5 → prev[5]=3 → prev[3]=2 → prev[2]=-1
得到序列：nums[2]=2, nums[3]=5, nums[5]=7, nums[6]=101
即 [2,5,7,101]
步骤7：算法复杂度
- 时间复杂度：O(n²)，需要两层循环
- 空间复杂度：O(n)，用于存储dp和prev数组
这种方法不仅能找到最长递增子序列的长度，还能通过prev数组回溯得到具体的序列内容，完美解决了我们的问题需求。