最长递增子序列：在一个序列中，选取若干元素（不要求连续，但必须保持原有先后顺序）组成的严格递增子序列里，长度最大的那一个（或其长度）。常简称 LIS。在算法题中常用动态规划或“二分 + 贪心（耐心排序思想）”求解。
/ˈlɔːŋɡɪst ɪnˈkriːsɪŋ ˈsʌbsɪkwəns/
The longest increasing subsequence of [3, 1, 2] has length 2.
序列 [3, 1, 2] 的最长递增子序列长度是 2。
Using binary search, we can compute the longest increasing subsequence in O(n log n) time.
使用二分查找，我们可以在 O(n log n) 时间内计算最长递增子序列。
这是一个由三个常见英语词组合而成的计算机术语：longest（最长的）+ increasing（递增的）+ subsequence（子序列）。其中 sequence 表示“序列”，前缀 sub- 有“次级/从属/部分”的含义，所以 subsequence 指“从序列中按顺序抽取出来的序列（不必连续）”。该术语在算法与组合数学语境中被固定使用。
Select Language