[−][src]Trait lis::LisExt
Extends AsRef<[T]>
with methods for generating longest increasing subsequences.
Provided methods
fn longest_increasing_subsequence(&self) -> Vec<usize> where
T: Ord,
T: Ord,
Returns indices of the longest increasing subsequence.
fn longest_increasing_subsequence_by<F, P>(&self, f: F, filter: P) -> Vec<usize> where
F: FnMut(&T, &T) -> Ordering,
P: FnMut(&T) -> bool,
F: FnMut(&T, &T) -> Ordering,
P: FnMut(&T) -> bool,
Returns indices of the longest increasing subsequence with a comparator function.
The closure filter
is called on each element. If it returns false
the element is
skipped, however indices are left intact.
This is O(n log n)
worst-case and allocates at most 2 * size_of<usize>() * n
bytes.
It is based on the method described by Michael L. Fredman (1975) in On computing the
length of longest increasing subsequences.
Example
use lis::LisExt; assert_eq!([2, 1, 4, 3, 5].longest_increasing_subsequence_by(|a, b| a.cmp(b), |_| true), [1, 3, 4]);