问题

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度
连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1

动态规划

动规五部曲分析如下：

  • 确定dp数组以及下标的含义

    • **dp[i]**：以下标**i**为结尾的数组的连续递增的子序列长度为**dp[i]**
    • 注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置

  • 确定递推公式

    • 如果nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度一定等于以i为结尾的数组的连续递增的子序列长度 + 1
    • dp[i + 1] = dp[i] + 1;
    • 因为本题要求连续递增子序列，所以就必要比较nums[i + 1]与nums[i]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）

  • dp数组如何初始化

    • 以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素

  • 确定遍历顺序

    • 从递推公式上可以看出，dp[i + 1]依赖dp[i]，所以一定是从前向后遍历
      1. for (int i = 0; i < nums.length - 1; i++) {
      2. if (nums[i + 1] > nums[i]) { // 连续记录
      3.    dp[i + 1] = dp[i] + 1; // 递推公式
      4. }
      5. }

  • 举例推导dp数组

    • 已输入nums = [1,3,5,4,7]为例，dp数组状态如下：

640 (1).webp

注意这里要取dp[i]里的最大值，所以dp[2]才是结果！

  1. class Solution {
  2.     public int findLengthOfLCIS(int[] nums) {
  3.         if (nums.length <= 1) 
  4.             return nums.length;
  6.         int result = 1;
  8.         int[] dp = new int[nums.length];
  9.         Arrays.fill(dp, 1);
  11.         for (int i = 0; i < nums.length - 1; i++) {
  12.             if (nums[i + 1] > nums[i]) { // 连续记录
  13.                 dp[i + 1] = dp[i] + 1;
  14.             }
  15.             if (dp[i + 1] > result)
  16.                 result = dp[i + 1];
  17.         }
  18.         return result;
  19.     }
  20. }
  • 时间复杂度：O(n)

  • 空间复杂度：O(n)

    贪心

    这道题目也可以用贪心来做，也就是遇到nums[i + 1] > nums[i]的情况，count++，否则count为1，记录count的最大值就可以了

    1. class Solution {
    2.   public int findLengthOfLCIS(int[] nums) {
    3.       if (nums.length <= 1) 
    4.           return nums.length;
    6.       int result = 1; // 连续子序列最少也是1
    8.       int count = 1;
    10.       for (int i = 0; i < nums.length - 1; i++) {
    11.           if (nums[i + 1] > nums[i]) { // 连续记录
    12.               count++;
    13.           } else { // 不连续，count从头开始
    14.               count = 1;
    15.           }
    16.           if (count > result) 
    17.               result = count;
    18.       }
    19.       return result;
    20.   }
    21. }

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)