线性动态规划：最长递增子序列的变种——最长递增子序列的长度与具体序列（允许重复元素） 题目描述 给定一个整数数组 nums （可能包含重复元素），要求找出其最长递增子序列（Longest Increasing Subsequence, LIS）的长度，并输出任意一个具体的最长递增子序列。注意：这里的“递增”允许相等元素连续出现（即非严格递增），但子序列必须是严格递增的（每个元素必须大于前一个元素）。例如，对于数组 [1, 3, 3, 2, 4] ，最长递增子序列可以是 [1, 3, 4] 或 [1, 2, 4] ，长度为 3。 解题过程 问题分析 最长递增子序列（LIS）问题要求找到一个子序列，其中元素按严格递增顺序排列，且长度最大。允许原数组包含重复元素，但子序列中不能使用相同值的元素来构成递增（因为严格递增要求后一个元素大于前一个）。 动态规划状态定义 定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。我们需要另一个数组 prev 来记录路径，以便最后回溯构造具体序列： prev[i] 存储在以 nums[i] 结尾的 LIS 中， nums[i] 的前一个元素的下标。 状态转移方程 对于每个位置 i ，遍历所有 j < i ： 如果 nums[i] > nums[j] （严格递增），则可以考虑将 nums[i] 接在以 nums[j] 结尾的 LIS 后面，形成更长的序列。即： \[ \text{如果 } dp[ j] + 1 > dp[ i] \text{，则设置 } dp[ i] = dp[ j] + 1,\ prev[ i ] = j. \] 如果 nums[i] <= nums[j] ，则跳过，因为无法构成递增。 初始化：每个位置的初始 dp[i] = 1 （单独一个元素构成子序列）， prev[i] = -1 （表示前面没有元素）。 计算过程示例 以 nums = [1, 3, 3, 2, 4] 为例： 初始化： dp = [1, 1, 1, 1, 1] ， prev = [-1, -1, -1, -1, -1] 。 i=0：无可比的前元素，保持 dp[0]=1 。 i=1：比较 j=0（1<3）， dp[1] = max(dp[1], dp[0]+1) = 2 ， prev[1]=0 。 i=2：比较 j=0（1<3）， dp[2]=2 ， prev[2]=0 ；j=1（3=3，不满足严格递增），跳过。 i=3：比较 j=0（1<2）， dp[3]=2 ， prev[3]=0 ；j=1（3>2，不满足），跳过；j=2（3>2，不满足），跳过。 i=4：比较 j=0（1<4）， dp[4]=2 ， prev[4]=0 ；j=1（3<4）， dp[4]=3 ， prev[4]=1 ；j=2（3<4），但 dp[2]+1=3 不大于当前 dp[4]=3 ，可保持或更新（任选一条路径，这里选 j=1）；j=3（2<4）， dp[3]+1=3 不大于当前值，跳过。 最终 dp = [1, 2, 2, 2, 3] ，最大长度 3。 回溯构造具体序列 找到 dp 最大值位置（i=4，长度=3），通过 prev 数组回溯： i=4，值4 → prev[ 4]=1，值3 → prev[ 1]=0，值1（prev[ 0 ]=-1，停止）。 逆序得到序列 [1, 3, 4] 。 复杂度分析 时间复杂度 O(n²)（两重循环），空间复杂度 O(n)（存储 dp 和 prev 数组）。 关键点 严格递增要求排除相等元素接续。 使用 prev 数组记录路径是输出具体序列的常用技巧。 允许重复元素不影响状态转移（判断条件始终是 nums[i] > nums[j] ）。