最长连续递增子序列的长度以及回溯获取正确的子序列数组

先贴一下代码，然后再讲一下这里难理解的点

function getLIS(nums) {
   const dp = []; // 存储递增子序列的末尾元素
   const pre = new Array(nums.length).fill(-1); // 记录每个元素的前驱节点
   const indices = []; // 记录 dp 数组中每个元素在原序列中的索引

   for (let i = 0; i < nums.length; i++) {
      debugger
      const num = nums[i];
      let left = 0,
         right = dp.length;
      while (left < right) {
         const mid = (left + right) >> 1;
         if (nums[indices[mid]] >= num) {
            right = mid;
         } else {
            left = mid + 1;
         }
      }
      if (left < dp.length) {
         indices[left] = i;
         dp[left] = num; // 更新 dp 数组
      } else {
         indices.push(i);
         dp.push(num); // 更新 dp 数组
      }
      if (left > 0) {
         pre[i] = indices[left - 1];
      }
   }

   const result = [];
   let current = indices[indices.length - 1];
   while (current !== -1) {
      result.push(nums[current]);
      current = pre[current];
   }
   result.reverse();

   return {
      length: dp.length, // 返回正确的长度
      sequence: result,
   };
}

console.log(getLIS([3, 1, 4, 1, 5, 9, 2, 6, 5]));

dp[i]表示当前长度的最长递增序列最后一个元素的最小值
也就是说，假如dp[4] = 5;那长度为4的时候，这个递增子序列的最后一个元素最小就是5，不可能还有比他还小的最后一个元素了。
所以，这个算法里面会有一个在dp数组中找到第一个比num大的数进行替换的操作，你比如对于[2, 3, 1]我们在处理1时会把dp[0]替换为1，可能有人会疑惑，为什么会把dp = [2, 3]替换为dp = [1, 3]，要注意dp数组代表了什么，代表的是当前长度的最长递增序列最后一个元素的最小值，也就是说当你处理1的时候，dp数组长度为1时，他的最后一个元素其实是可以取到1的，这个算法里面看似是个dp数组，但其实不是传统意义上的动态规划，每一步操作都有可能去改变前面的dp数组的状态，所以才导致了这种困惑。
然后就是回溯问题，pre数组存放的是num元素在当前dp数组中前一个元素在num数组中的索引，这里其实是可以保证前驱节点一定在当前节点的前面的，因为就算你替换掉了前驱节点，因为没有替换当前节点，所以他的前驱节点是不会变的。