最长递增子序列的变种——最长递增子序列的长度与具体序列（允许重复元素） 题目描述： 给定一个整数数组nums，找到最长递增子序列（LIS）的长度，并返回其中一个具体的LIS序列。注意：这个变种问题允许子序列中的元素可以重复出现（即非严格递增），但要求返回的序列必须是原数组中的实际元素按原顺序组成的。 解题过程： 问题理解： 我们需要找到数组中最长的递增子序列（允许相等元素），并返回这个序列本身。这与标准LIS问题不同，标准问题通常只要求长度或任意一个序列，而这里需要构造出具体的序列。 动态规划状态定义： 定义dp[ i ]为以第i个元素结尾的最长递增子序列的长度。 状态转移方程： 对于每个位置i，我们需要检查所有j < i的元素： 如果nums[ j] ≤ nums[ i ]（允许相等），那么： dp[ i] = max(dp[ i], dp[ j ] + 1) 记录路径信息： 为了能够回溯构造具体的序列，我们需要记录每个位置的前驱位置。定义prev[ i]表示在以nums[ i]结尾的最长递增子序列中，nums[ i ]的前一个元素的位置。 算法步骤： 初始化dp数组全为1（每个元素本身构成长度为1的子序列） 初始化prev数组全为-1（表示没有前驱） 遍历数组，对于每个i： 遍历所有j < i 如果nums[ j] ≤ nums[ i]且dp[ j] + 1 > dp[ i ]： 更新dp[ i] = dp[ j ] + 1 记录prev[ i ] = j 找到dp数组中的最大值及其位置 通过prev数组回溯构造具体序列 示例演示： 考虑数组nums = [ 3, 1, 2, 2, 4, 3, 5 ] 初始化： dp = [ 1, 1, 1, 1, 1, 1, 1 ] prev = [ -1, -1, -1, -1, -1, -1, -1 ] 处理过程： i=0: 第一个元素，保持初始状态 i=1: nums[ 1]=1 < nums[ 0]=3，但dp[ 0]+1=2 > dp[ 1]=1，更新dp[ 1]=2, prev[ 1 ]=0 i=2: 比较j=0,1 j=0: nums[ 0]=3 > nums[ 2 ]=2，跳过 j=1: nums[ 1]=1 ≤ nums[ 2]=2，dp[ 1]+1=3 > dp[ 2]=1，更新dp[ 2]=3, prev[ 2 ]=1 i=3: 比较j=0,1,2 j=2: nums[ 2]=2 ≤ nums[ 3]=2，dp[ 2]+1=4 > dp[ 3]=1，更新dp[ 3]=4, prev[ 3 ]=2 i=4: 比较所有j <4 j=3: nums[ 3]=2 ≤ nums[ 4]=4，dp[ 3]+1=5 > dp[ 4]=1，更新dp[ 4]=5, prev[ 4 ]=3 i=5: 比较所有j <5 找到满足条件的最优j=1: dp[ 1 ]+1=3 i=6: 比较所有j <6 j=4: nums[ 4]=4 ≤ nums[ 6]=5，dp[ 4]+1=6 > dp[ 6]=1，更新dp[ 6]=6, prev[ 6 ]=4 最终dp = [ 1, 2, 3, 4, 5, 3, 6 ] 最大值6出现在位置6，通过prev回溯： 6→4→3→2→1→0 得到序列：[ 3, 1, 2, 2, 4, 5 ] 复杂度分析： 时间复杂度：O(n²)，需要两层嵌套循环 空间复杂度：O(n)，用于存储dp和prev数组 优化考虑： 对于只需要长度的情况，可以使用O(nlogn)的贪心+二分查找算法，但为了构造具体序列，O(n²)的解法是必要的。