[300] 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n^2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

严格最长升序子序列，这道题如果是求连续最长升序子序列则非常简单，对数组进行一次双指针查询，往后遍历到小于前一个数为止记录两指针差值即可。

但这里的升序序列不一定连续，例如[2，5，3，4]这个数组就能分出[2,3,4]的升序子序列，如果再用上述办法暴力解的话就需要再多一次循环判断是否需要纳入当前快指针进入子序列。同时在这里也可以看出这中判断是存在最优子结构的，因此很容易联想到用动态规划来解。

构建一个一维数组dp[i]，表示以第i个数字为结尾的最长上升子序列的长度。dp[i]的值应为i之前所有比nums[i]小的值所对应的子序列长度中最长的+1。

这样很容易得到了状态转移方程：dp[i] = max(dp[j] + 1) (0<j<i && nums[j] < nums[i])

这样dp[n]求的是以数组最后一个数字结尾的最长升序子序列，如果要求整个数组的，只需要取dp中最大的值即可。

function lengthOfLIS(nums: number[]): number {
  const len = nums.length;
  const dp = Array(len).fill(1);
  let max = 1;
  // Sn = (Sn-1, An)为递增子序列 ? Sn-1 + 1 : Sn-1
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      // 此时可以凑出递增子序列
      if (nums[i] > nums[j]) {
        // 选出 以nums[i]结尾的 最大递增子序列长度
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    max = Math.max(max, dp[i]);
  }
  return max;
}

题目要求我们优化算法，将算法的时间复杂度降低到O(nlogn)。一看到logn的优化自然就想到了二分查找。

我们可以维护一个最小递增子序列LIS，遍历nums数组时，使用左边界二分法判断当前元素是否可以替换LIS中的元素，形成新的最小递增子序列。

当前元素比LIS中的所有元素都大时，说明递增序列的长度可以增加，此时将该元素push进入LIS。

最后返回该LIS的长度，即为nums最大子序列的长度了。注意，这里LIS中元素的顺序并不一定是真实的LIS，只是长度相等而已。

function lengthOfLIS(nums: number[]): number {
  // 维护一个最小递增子序列
  const lis: number[] = [];
  // Sn = (Sn-1, An)为递增子序列 ? Sn-1 + 1 : Sn-1
  for (let i = 0; i < nums.length; i++) {
    let left = 0;
    let right = lis.length - 1;
    // 求左边界的二分法
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (lis[mid] < nums[i]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    if (left >= lis.length) {
      // 边界越界，说明此时子 LIS 中不存在比 nums[i] 大的数，LIS 数组增加一位
      lis.push(nums[i]);
    } else {
      // 否则更新该 LIS 位置上的数字
      lis[left] = nums[i];
    }
  }
  return lis.length;
}