300.最长递增子序列

链接：300.最长递增子序列
难度：Medium
标签：数组、二分查找、动态规划
简介：给定一个无序的整数数组，找到其中最长上升子序列的长度。

题解 1 - typescript

• 编辑时间：2021-09-04
• 执行用时：76ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：找尽可能长的序列。

function lengthOfLIS(nums: number[]): number {
  const list = [nums[0]];
  for (const num of nums) list[find(num)] = num;
  return list.length;
  function find(num: number): number {
    let l = 0;
    let r = list.length - 1;
    if (num > list[r]) return list.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (list[mid] >= num) r = mid;
      else l = mid + 1;
    }
    return l;
  }
}

题解 2 - typescript

• 编辑时间：2021-09-04
• 执行用时：76ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：找尽可能长的序列。

function lengthOfLIS(nums: number[]): number {
  const list = [nums[0]];
  for (const num of nums) list[find(num)] = num;
  return list.length;
  function find(num: number): number {
    let l = 0;
    let r = list.length - 1;
    if (num > list[r]) return list.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (list[mid] >= num) r = mid;
      else l = mid + 1;
    }
    return l;
  }
}

题解 3 - typescript

• 编辑时间：2021-09-04
• 执行用时：192ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：动态规划。

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  let ans = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
        ans = Math.max(ans, dp[i]);
      }
    }
  }
  return ans;
}

题解 4 - javascript

• 编辑时间：2020-05-10
• 执行用时：72ms
• 内存消耗：34.6MB
• 编程语言：javascript
• 解法介绍：递推的基础上，判断前一项是否值小于当前项。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const len = nums.length;
  if (len === 0) return 0;
  const dp = [1];
  let max,
    res = 1;
  for (let i = 1; i < len; i++) {
    const num = nums[i];
    max = 0;
    for (let j = 0; j < i; j++) {
      if (nums[j] >= num) continue;
      max = max > dp[j] ? max : dp[j];
    }
    dp[i] = max + 1;
    res = res > dp[i] ? res : dp[i];
  }
  return res;
};

题解 5 - typescript

• 编辑时间：2021-09-04
• 执行用时：192ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：动态规划。

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  let ans = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
        ans = Math.max(ans, dp[i]);
      }
    }
  }
  return ans;
}