Crate ris 

Computes the Longest Increasing Subsequence (LIS) and other monotonic subsequences.

This crate provides an algorithm with O(N log N) time complexity to find the longest increasing, decreasing, or custom monotonic subsequence.

Examples

Using the slice extension trait LisExt:

use ris::LisExt;

let seq = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

// Get the indices of the LIS
let indices = seq.lis_indices();
assert_eq!(indices, [3, 6, 9, 10]);

// Get the values directly
let values = seq.lis_values();
assert_eq!(values, [1, 2, 3, 5]);

// Get the length only
let length = seq.lis_length();
assert_eq!(length, 4);

Using the iterator extension trait IteratorLisExt:

use ris::IteratorLisExt;

let seq = [3, 1, 4, 1, 5, 9];
let values = seq.into_iter().lis();
assert_eq!(values, [1, 4, 5, 9]);

Traits

IteratorLisExt

Extension trait to compute longest monotonic subsequences on iterators.

LisExt

Extension trait to compute longest monotonic subsequences on slices.

Functions

lis

Computes the indices of the longest subsequence that satisfies the is_less condition.

lis_length

Computes only the length of the longest subsequence that satisfies the is_less condition.