最长递增子序列的变种：最长递增子序列的长度与具体序列（允许重复元素） 题目描述： 给定一个整数数组nums，找到其中最长的严格递增子序列的长度，并输出任意一个这样的最长递增子序列。注意子序列不要求连续，但必须是严格递增的（即每个元素都严格大于前一个元素）。数组可能包含重复元素。 例如： 输入：nums = [ 10,9,2,5,3,7,101,18 ] 输出：长度 = 4，一个可能的子序列是 [ 2,3,7,101 ] 解题过程： 步骤1：理解问题与定义状态 我们需要找到最长的严格递增子序列。由于子序列不要求连续，我们需要一个动态规划数组来记录以每个位置结尾的最长递增子序列长度。 定义： dp[ i]：表示以nums[ i ]结尾的最长递增子序列的长度 prev[ i]：记录在最长递增子序列中，nums[ i ]的前一个元素的位置 步骤2：状态转移方程 对于每个位置i，我们需要检查所有j < i： 如果nums[ i] > nums[ j]，那么我们可以将nums[ i]接在以nums[ j ]结尾的递增子序列后面，形成更长的子序列。 状态转移方程： dp[ i] = max(dp[ j] + 1)，对于所有0 ≤ j < i 且 nums[ i] > nums[ j ] 同时记录前驱： prev[ i] = j（其中j是使dp[ j ] + 1最大的那个索引） 步骤3：初始化 每个元素本身至少可以形成一个长度为1的递增子序列： dp[ i ] = 1（对于所有i） prev[ i ] = -1（表示没有前驱，即这是子序列的第一个元素） 步骤4：算法实现 我们可以用两层循环来实现： 外层循环遍历每个位置i（从0到n-1） 内层循环遍历所有j < i 如果nums[ i] > nums[ j]且dp[ j] + 1 > dp[ i]，则更新dp[ i]和prev[ i ] 步骤5：记录结果 在填充dp数组的过程中，我们需要记录： 最长递增子序列的长度max_ len 最长递增子序列结束的位置max_ index 步骤6：重建具体序列 从max_ index开始，通过prev数组反向追踪，就可以重建出一个具体的最长递增子序列。 步骤7：示例演示 以nums = [ 10,9,2,5,3,7,101,18 ]为例： 初始化： dp = [ 1,1,1,1,1,1,1,1 ] prev = [ -1,-1,-1,-1,-1,-1,-1,-1 ] i=0: 没有j<0，保持dp[ 0 ]=1 i=1: nums[ 1 ]=9 j=0: nums[ 1]=9 < nums[ 0 ]=10，不满足递增 dp = [ 1,1,1,1,1,1,1,1 ] i=2: nums[ 2 ]=2 j=0: 2 <10，不满足 j=1: 2 <9，不满足 dp = [ 1,1,1,1,1,1,1,1 ] i=3: nums[ 3 ]=5 j=0: 5 <10，不满足 j=1: 5 <9，不满足 j=2: 5>2，dp[ 2]+1=2 > dp[ 3 ]=1 dp[ 3]=2, prev[ 3 ]=2 dp = [ 1,1,1,2,1,1,1,1 ] i=4: nums[ 4 ]=3 j=0: 3 <10，不满足 j=1: 3 <9，不满足 j=2: 3>2，dp[ 2]+1=2 > dp[ 4 ]=1 dp[ 4]=2, prev[ 4 ]=2 dp = [ 1,1,1,2,2,1,1,1 ] i=5: nums[ 5 ]=7 j=0: 7 <10，不满足 j=1: 7 <9，不满足 j=2: 7>2，dp[ 2 ]+1=2 j=3: 7>5，dp[ 3 ]+1=3 > 当前值 dp[ 5]=3, prev[ 5 ]=3 j=4: 7>3，dp[ 4 ]+1=3，与当前值相等，可以更新也可以不更新 dp = [ 1,1,1,2,2,3,1,1 ] i=6: nums[ 6 ]=101 检查所有j<6，找到最大的dp[ j ]+1 最终：dp[ 5 ]+1=4最大 dp[ 6]=4, prev[ 6 ]=5 dp = [ 1,1,1,2,2,3,4,1 ] i=7: nums[ 7 ]=18 检查所有j<7，找到最大的dp[ j ]+1 最终：dp[ 5 ]+1=4最大 dp[ 7]=4, prev[ 7 ]=5 dp = [ 1,1,1,2,2,3,4,4 ] 步骤8：提取结果 max_ len = 4 max_ index = 6（或7，两者都可以） 从max_ index=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 ] 这个算法的时间复杂度是O(n²)，空间复杂度是O(n)。通过记录prev数组，我们不仅能得到最长递增子序列的长度，还能重建出具体的序列。