LIS
最长上升子序列（计算机科学）
最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。
实现
使用动态规划算法。有两种，时间复杂度分别为O(n^2)与O(n log n)，空间复杂度均为O(n)。
朴素DP算法，O(n^2)：
优化DP算法，O(n log n)：
应用
LIS经常用于确定一个代价最小的调整方案，使一个序列变为升序。只需要固定LIS中的元素，调整其他元素即可。
参考资料
最新修订时间：2023-07-04 16:00
条目作者
小编
目录
概述
实现
参考资料

Copyright©2024 闽ICP备2024072939号-1