最长递增子序列的变种：最长连续递增子序列 题目描述 给定一个无序的整数数组，找到其中最长的连续递增子序列的长度。连续递增子序列是指子序列中的元素在原数组中连续排列，并且严格递增。例如，对于数组 [ 1, 3, 5, 4, 7]，最长的连续递增子序列是 [ 1, 3, 5 ]，长度为 3（注意：虽然 1, 3, 5, 7 也是递增的，但 5 和 7 在原数组中不连续，因此不符合“连续”条件）。 解题过程 问题分析 与标准最长递增子序列（LIS）不同，本题要求子序列在原数组中连续排列。这意味着我们只需检查相邻元素是否递增，而无需考虑非连续元素。这简化了问题，因为子序列的连续性使其天然具有最优子结构：以第 i 个元素结尾的连续递增子序列的长度，仅取决于第 i-1 个元素是否小于第 i 个元素。 状态定义 定义 dp[ i] 表示以第 i 个元素结尾的最长连续递增子序列的长度。我们的目标是求所有 dp[ i ] 中的最大值。 状态转移方程 如果 nums[ i] > nums[ i-1]，说明第 i 个元素可以接在以第 i-1 个元素结尾的连续递增子序列后，形成更长的子序列：dp[ i] = dp[ i-1 ] + 1。 如果 nums[ i] ≤ nums[ i-1]，说明连续递增序列在第 i 个元素处中断，此时只能以第 i 个元素单独作为一个子序列：dp[ i ] = 1。 转移方程简写为： \[ dp[ i ] = \begin{cases} dp[ i-1] + 1 & \text{if } nums[ i] > nums[ i-1 ] \\ 1 & \text{otherwise} \end{cases} \] 初始化 第一个元素自身构成一个长度为 1 的连续递增子序列，因此 dp[ 0 ] = 1。 计算顺序与示例 以 nums = [ 1, 3, 5, 4, 7 ] 为例： i=0: dp[ 0] = 1（子序列 [ 1 ]）。 i=1: nums[ 1]=3 > nums[ 0]=1 ⇒ dp[ 1] = dp[ 0] + 1 = 2（子序列 [ 1,3 ]）。 i=2: nums[ 2]=5 > nums[ 1]=3 ⇒ dp[ 2] = dp[ 1] + 1 = 3（子序列 [ 1,3,5 ]）。 i=3: nums[ 3]=4 ≤ nums[ 2]=5 ⇒ dp[ 3] = 1（子序列 [ 4 ]）。 i=4: nums[ 4]=7 > nums[ 3]=4 ⇒ dp[ 4] = dp[ 3] + 1 = 2（子序列 [ 4,7 ]）。 最终，max(dp) = max(1,2,3,1,2) = 3。 优化 由于 dp[ i] 仅依赖 dp[ i-1]，可优化空间复杂度至 O(1)：用一个变量 curr_ len 记录当前连续递增序列长度，max_ len 记录全局最大值。遍历数组时更新： 若 nums[ i] > nums[ i-1]，curr_ len++；否则 curr_ len = 1。 更新 max_ len = max(max_ len, curr_ len)。 关键点 连续递增子序列的连续性简化了状态转移，仅需比较相邻元素。 贪心思想：只要递增就扩展序列，否则重新开始计数。