longest-increasing-subsequence

最长递增子序列

最长递增子序列问题是要在一个给定序列中找到一个子序列，其中子序列的元素按顺序排列，从低到高，且子序列尽可能长。这个子序列不一定是连续的，也不一定是唯一的。

— 维基百科

例如，考虑这个整数序列

2, 9, 4, 7, 3, 4, 5

这个序列的最长递增子序列（LIS）是 2, 3, 4, 5。

请注意，不一定总是存在一个 唯一的 LIS。考虑这个序列

2, 6, 5

在这个序列中，2, 5 和 2, 6 都是 LIS。

API

这个包公开了两个函数，用于在切片中查找最长递增子序列

1. 高级、易用的 lis 函数接受任何 T: Ord 的切片，并返回一个包含该切片索引的向量作为 LIS。

2. 低级 lis_with 函数接受一个自定义比较器，并允许您自己分配（这使您可以选择重用分配或使用自定义分配器）。

这两个函数使用相同的底层算法。它们在 O(n log n) 时间内执行，并使用 O(n) 内存。

示例

use longest_increasing_subsequence::lis;

let xs = vec![9, 2, 8, 3, 5];
for i in lis(&xs) {
    println!("{} at index {}", xs[i], i);
}

// Prints:
// 2 at index 1
// 3 at index 3
// 5 at index 4