【算法题-困难】最长递增子序列

困难算法题，最长递增子序列，使用 JavaScript 语言编写

题目

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入格式

1 <= nums.length <= 2000 -10000 <= nums[i] <= 10000

输出格式

最长严格递增子序列的长度

输入样例

10 9 2 5 3 7 101 18

输出样例

4

分析

解答

// 这是题目要求的输入格式
let inputs = `
10 9 2 5 3 7 101 18
`;
const nums = inputs.trim().split(' ').map(Number);

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

function lengthOfLIS2(nums) {
  const stack = [];
  let ret = 0;
  while (nums.length > 0) {
    let f = nums.shift();
    while (stack.length > 0 && stack[stack.length - 1] >= f) {
      stack.pop();
    }
    stack.push(f);
    ret = Math.max(ret, stack.length);
  }
  return ret;
}

// 示例
console.log(lengthOfLIS2(nums)); // 输出 4