力扣链接：300.最长递增子序列

难度：⭐⭐

✏️ 方法一：更推荐方法二

解题关键词：动态规划

解题思路：每走一个元素，然后用当前元素和前面所有元素比一下，如果比前面元素大，那么说明可以链接到某个元素最长子序列中，不断找最大的。

function lengthOfLIS(nums: number[]): number {
  // 存放最大值
  let result = 1;
  const length = nums.length;
  // 初始化一个 dp 数组，存放到每个元素最长的递增子序列长度
  const dp = new Array(length).fill(1);

  for (let i = 1; i < length; i++) {
    // 前面走过的，遍历一下
    for (let j = 0; j < i; j++) {
      // 如果当前这个元素比前面元素大，那么更新一下最大值
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
        result = Math.max(dp[i], result);
      }
    }
  }

  return result;
}

✏️ 方法二：

解题关键词：贪心、二分查找

解题思路：从左往右遍历 nums，维护一个 dp 数组（单调递增的），里面存放着最长子序列（可能顺序不是正确的），如果当前遍历到的数字比数组中最后一个大，将当前数字加入数组中，如果比最后一个数字小，那么要找到数组中比它自身小的最后一个元素，然后将找到的pos位置后面一个替换为当前数字。在查找比指定元素小的最后一个元素时，使用二分查找，因为数组是单调递增的。

function lengthOfLIS(nums: number[]): number {
  if (!nums.length) return 0;
  // 存放最长子增序列，可能不是正确的
  const dp = [nums[0]];

  for (let i = 1; i < nums.length; i++) {
    // 如果当前元素比数组中最后一个元素大，加入数组
    if (nums[i] > dp[dp.length - 1]) {
      dp.push(nums[i]);
    } else {
      // 找到了比指定元素小的数组中最后一个元素
      const targetIndex = findIndex(dp, nums[i]);
      // 将后面元素替换掉
      dp.splice(targetIndex + 1, 1, nums[i]);
    }
  }

  return dp.length;
}

// 二分查找最后一个比 target 元素小的元素位置
function findIndex(nums: number[], target: number) {
  // 默认为 -1，如果 pos 返回 -1，代表所有元素都比 target 大，这个时候要替换数组中第一个位置，因为上面会 +1，所以这里默认为 -1
  let pos = -1;
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((right - left) / 2) + left;

    if (nums[mid] < target) {
      pos = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return pos;
}