#increasing #longest #subsequence #sequence #find #input #lis

longest-increasing-subsequence

Find a longest increasing subsequence of some input sequence

1 unstable release

0.1.0 Apr 3, 2019

#1070 in Algorithms

Download history 4099/week @ 2024-03-14 4953/week @ 2024-03-21 5453/week @ 2024-03-28 5065/week @ 2024-04-04 5815/week @ 2024-04-11 5325/week @ 2024-04-18 6027/week @ 2024-04-25 5452/week @ 2024-05-02 4732/week @ 2024-05-09 5412/week @ 2024-05-16 5297/week @ 2024-05-23 5448/week @ 2024-05-30 4987/week @ 2024-06-06 5082/week @ 2024-06-13 5450/week @ 2024-06-20 3912/week @ 2024-06-27

20,596 downloads per month
Used in 173 crates (5 directly)

MIT/Apache

12KB
80 lines

longest-increasing-subsequence

Build Status

Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Wikipedia

For example, consider this sequence of integers:

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

The longest increasing subsequence (LIS) for this sequence is 2, 3, 4, 5.

Note that there is not always a singular LIS. Consider this sequence:

2, 6, 5

In this sequence, both 2, 5 and 2, 6 are LISs.

API

This crate exposes two functions for finding a longest increasing subsequence within a slice:

  1. The high-level, easy-to-use lis function takes any slice of T: Ord and returns the LIS as a vector of indices into that slice.

  2. The low-level lis_with function takes a custom comparator and lets you bring your own allocations (which lets you choose to reuse allocations or use a custom allocator).

Both functions use the same underlying algorithm. They execute in O(n log n) time and use O(n) memory.

Example

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

No runtime deps