最长递增子序列的变种：最长连续递增子序列的个数 题目描述 给定一个整数数组 nums，找到最长连续递增子序列（LCIS）的个数。连续递增子序列是指索引连续且元素严格递增的子数组。例如，数组 [ 1,3,5,4,7] 的最长连续递增子序列是 [ 1,3,5] 和 [ 4,7 ]，长度均为 3，因此个数为 2。注意：子序列必须是连续的（即子数组），且严格递增。 解题过程 问题分析 我们需要找到所有最长的连续递增子数组（LCIS）的数量。关键点在于： 连续性：子序列必须是原数组中的连续段。 严格递增：每个元素必须严格大于前一个元素。 统计个数：需要统计所有长度达到最大值的LCIS的个数。 动态规划状态定义 定义 dp_ len[ i ] 表示以第 i 个元素结尾的最长连续递增子数组的长度。 定义 dp_ cnt[ i] 表示以第 i 个元素结尾的最长连续递增子数组的个数（注意：这里“个数”指以 i 结尾的、长度等于 dp_ len[ i ] 的子数组个数）。 状态转移方程 初始化：每个元素自身构成一个长度为 1 的连续递增子数组，因此 dp_ len[ i] = 1，dp_ cnt[ i ] = 1（因为单个元素的子数组只有一种可能）。 对于 i > 0： 如果 nums[ i] > nums[ i-1]，说明可以将 nums[ i ] 接在以 i-1 结尾的连续递增子数组之后： dp_ len[ i] = dp_ len[ i-1 ] + 1 dp_ cnt[ i] = dp_ cnt[ i-1 ] // 因为以 i 结尾的LCIS只是将以 i-1 结尾的LCIS延长一个元素，个数不变 如果 nums[ i] <= nums[ i-1]，则无法接续，只能以 nums[ i ] 单独开头： dp_ len[ i ] = 1 dp_ cnt[ i ] = 1 统计最终结果 遍历数组，维护一个全局最大值 max_ len，表示找到的最长连续递增子数组的长度。 同时，初始化结果 count = 0。 对于每个位置 i： 如果 dp_ len[ i] > max_ len，更新 max_ len = dp_ len[ i]，并重置 count = dp_ cnt[ i ] 如果 dp_ len[ i] == max_ len，则 count += dp_ cnt[ i ] 举例说明 以 nums = [ 1,3,5,4,7 ] 为例： i=0: dp_ len=1, dp_ cnt=1 → max_ len=1, count=1 i=1: 3>1 → dp_ len=2, dp_ cnt=1 → max_ len=2, count=1 i=2: 5>3 → dp_ len=3, dp_ cnt=1 → max_ len=3, count=1 i=3: 4<5 → dp_ len=1, dp_ cnt=1 → max_ len=3, count=1 i=4: 7>4 → dp_ len=2, dp_ cnt=1 → 但 dp_ len=2 < max_ len=3，不更新 count 最终 count=1？但实际有 [ 1,3,5] 和 [ 4,7 ] 两个长度为 3 的LCIS。问题出在哪里？ 注意 ：当 i=4 时，虽然 dp_ len[ 4]=2，但以 4 结尾的LCIS [ 4,7] 实际上长度是 2，并不是一个独立的长度为 3 的LCIS。我们需要的是所有长度为 max_ len 的连续子数组的个数，而不是以每个位置结尾的个数之和。但在这个例子中，[ 1,3,5] 对应 i=2，[ 4,7] 对应 i=4 吗？不对，[ 4,7 ] 的长度是 2，不是 3。所以我们的例子举错了！ 重新举例：nums = [ 1,3,5,4,7,8 ] 最长连续递增子数组是 [ 4,7,8 ]，长度=3。 还有 [ 1,3,5 ] 长度=3。 所以个数=2。 计算过程： i=0: len=1, cnt=1 → max_ len=1, count=1 i=1: 3>1 → len=2, cnt=1 → max_ len=2, count=1 i=2: 5>3 → len=3, cnt=1 → max_ len=3, count=1 i=3: 4<5 → len=1, cnt=1 → max_ len=3, count=1 i=4: 7>4 → len=2, cnt=1 → max_ len=3, count=1 i=5: 8>7 → len=3, cnt=1 → max_ len=3, count=1+1=2 正确！所以当 i=5 时，dp_ len[ 5]=3，且等于 max_ len，因此 count 加上 dp_ cnt[ 5 ]=1。 算法复杂度 时间复杂度：O(n)，空间复杂度：O(n)（可以优化到 O(1) 只记录前一个状态）。 关键点 每个位置 i 的 dp_ cnt[ i] 实际上是以 i 结尾的、长度为 dp_ len[ i] 的连续递增子数组的个数（总是为 1，因为连续子数组的起始位置被唯一确定：i - dp_ len[ i ] + 1）。 因此，dp_ cnt[ i] 始终等于 1，可以省略。最终结果就是统计有多少个 i 满足 dp_ len[ i] == max_ len。 简化版解法 实际上，dp_ cnt[] 数组是不必要的，因为对于每个位置 i，以 i 结尾的最长连续递增子数组是唯一的（起始位置固定）。只需维护 dp_ len[]，然后统计 dp_ len[ i ] 等于全局最大值的 i 的个数即可。 希望这个讲解帮助你理解了最长连续递增子序列个数的统计方法！