面试题库 › 算法 / 大模型 › 最长递增子序列及常见变种

最长递增子序列及常见变种

难度 ★★★在 2 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

美团1文远知行1

常见岗位:推荐搜索广告、C/C++ 软件开发

答案要点

  1. O(n²) DP:dp[i] 为以 i 结尾的 LIS 长度,枚举前面更小的元素转移
  2. O(n log n):tails[k] 是长度 k+1 的递增子序列的最小结尾,二分替换或追加
  3. 非严格递增:二分改为找第一个大于当前值的位置
  4. 输出序列记录前驱回溯;求个数时额外维护计数数组
  5. 信封嵌套:宽升序、宽相同时高降序排序,再对高求 LIS

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题