题目描述

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= $10^4$
  • -$10^9$ <= nums[i] <= $10^9$

暴力

鉴于题目的输入规模在 $10^4$，估计 O($n^2$) 大概在 $10^8$, 所以暴力算法是可以被接受的

所以很简单，只需要枚举所有的连续子序列即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function (nums) {
  let ans = 1;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      let prev = nums[j - 1];
      let cur = nums[j];
      if (cur > prev) {
        ans = Math.max(j - i + 1, ans);
      } else break;
    }
  }
  return ans;
};

每到一个新的数组元素，与前一个数组元素作比较，如果确实更大，那么将答案序列延长一位，将该元素假如答案序列数组，进行下个元素的比较

动态规划

定义 dp 数组为包含下标为 i 的元素，且截止到该元素的最长递增序列

故如果该元素大于该元素前面一个元素的值，那么可以在前面一个元素的答案上拼接到该元素，如果不大于，那么答案就是 1

最后筛选一下最大值就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function (nums) {
  let dp = Array.from({ length: nums.length }, () => 1);
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      dp[i] = dp[i - 1] + 1;
    }
  }
  let ans = 0;
  for (let i = 0; i < dp.length; i++) {
    ans = Math.max(dp[i], ans);
  }
  return ans;
};

从 O($n^2$) 优化到 O(n)

建议看完立即去看 300 题，最长递增子序列