最长递增子序列

题目：

最长递增子序列（Longest Increasing Subsequence，简称LIS）是在一个数列中找到一个最长的子序列（不一定连续），使得这个子序列中的所有元素都是按照严格递增的顺序排列的。例如，在数列 [10, 9, 2, 5, 3, 7, 101, 18] 中，最长递增子序列是 [2, 3, 7, 101]，其长度为4。

思路：

1.动态规划法

动态规划的基本思想是，
对于数列中的每一个元素，我们记录下以该元素结尾的最长递增子序列的长度。然后，对于每一个新的元素，我们检查在它之前的元素，找到一个最长的递增子序列，该序列可以通过添加这个新元素来延长。这样，我们就可以构建出一个最长递增子序列。

动态规划解法的时间复杂度是 O(n^2)，其中 n 是数列的长度。

使用动态规划方法：

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

这段代码会创建一个数组dp，其中dp[i]表示以nums[i]结尾的最长递增子序列的长度。对于数组中的每个元素，它都会查找在它之前的所有元素，找到可以形成递增子序列的最长长度，并更新dp[i]。最后，它返回dp数组中的最大值，即整个数组的最长递增子序列的长度。

2. 二分查找法

使用二分查找来优化最长递增子序列（LIS）的解法是一种效率更高的方法，可以将时间复杂度从 O(n^2) 降低到 O(n \log n)。这种方法结合了贪心算法和二分查找，其核心思想是维护一个数组，该数组在任何时刻都保存着当前找到的所有递增子序列的最小可能尾数。
以下是这种优化方法的步骤：

1. 初始化一个空数组 tails，用于保存最小尾数。
2. 遍历原始数组，对于每个元素执行以下操作：
   • 使用二分查找在 tails 中找到第一个大于或等于当前元素的位置。
   • 如果找到这样的位置，用当前元素替换该位置的值（这意味着存在一个更小的值作为相同长度的递增子序列的尾数）。
   • 如果没有找到这样的位置，将当前元素添加到 tails 的末尾（这意味着我们找到了一个更长的递增子序列）。
3. 遍历结束后，tails 数组的长度即为最长递增子序列的长度。

下面是JavaScript中实现这一优化方法的代码示例：

function lengthOfLIS(nums) {
  let tails = [];
  for (let x of nums) {
    let i = 0, j = tails.length;
    while (i != j) {
      let m = (i + j) >> 1;
      if (tails[m] < x)
        i = m + 1;
      else
        j = m;
    }
    tails[i] = x;
    if (i === tails.length) tails.push(x);
  }
  return tails.length;
}

这段代码通过维护一个有序数组 tails，并使用二分查找来优化查找过程，从而提高了算法的效率。