dsalgo/
longest_increasing_subsequence.rs

1use crate::binary_search_on_slice_bisection_of_ng_ok::binary_search;
2
3pub(self) fn find_longest_subsequence<T: Copy, F: Fn(&T, &T) -> bool>(
4    slice: &[T],
5    binary_relation: F,
6) -> Vec<T> {
7    let mut result = vec![None; slice.len()];
8
9    for &value in slice {
10        let is_ok = |x: &Option<T>| {
11            if let Some(x) = x {
12                binary_relation(x, &value)
13            } else {
14                true
15            }
16        };
17
18        let index = binary_search(&is_ok, &result);
19
20        result[index] = Some(value);
21    }
22
23    let index = binary_search(&|value: &Option<T>| value.is_none(), &result);
24
25    result[..index].iter().map(|x| x.unwrap()).collect()
26}
27
28pub fn longest_increasing_subsequence<T: PartialOrd + Clone + Copy>(
29    slice: &[T]
30) -> Vec<T> {
31    find_longest_subsequence(slice, |x, value| x >= value)
32}
33
34pub fn longest_non_decreasing_subsequence<T: PartialOrd + Clone + Copy>(
35    slice: &[T]
36) -> Vec<T> {
37    find_longest_subsequence(slice, |x, value| x > value)
38}
39
40#[cfg(test)]
41
42mod tests {
43
44    use super::*;
45
46    #[test]
47
48    fn test() {
49        let arr = [4, 2, 8, 5, 6, 6];
50
51        assert_eq!(longest_increasing_subsequence(&arr), vec![2, 5, 6]);
52
53        assert_eq!(longest_non_decreasing_subsequence(&arr), vec![2, 5, 6, 6]);
54    }
55}
dsalgo/longest_increasing_subsequence.rs

dsalgo/
longest_increasing_subsequence.rs
