haar_lib/algo/
lis.rs

1//! 最長増加部分列
2
3use crate::algo::bsearch_slice::BinarySearch;
4
5/// 列の最長増加部分列の一つを求める。
6///
7/// **Time complexity** $O(|a| \log |a|)$
8pub fn lis<T>(a: &[T]) -> Vec<usize>
9where
10    T: Ord + Copy,
11{
12    let n = a.len();
13    let mut dp = vec![];
14    let mut pos = vec![];
15    let mut prev = vec![None; n];
16
17    for (i, x) in a.iter().enumerate() {
18        if dp.is_empty() || dp.last().unwrap() < &x {
19            dp.push(x);
20            if let Some(&last) = pos.last() {
21                prev[i] = Some(last);
22            }
23            pos.push(i);
24        } else {
25            let k = dp.lower_bound(&x);
26            dp[k] = x;
27            if k > 0 {
28                prev[i] = Some(pos[k - 1]);
29            }
30            pos[k] = i;
31        }
32    }
33
34    let mut ret = vec![];
35    let mut i = Some(*pos.last().unwrap());
36    while let Some(j) = i {
37        ret.push(j);
38        i = prev[j];
39    }
40
41    ret.reverse();
42    ret
43}
44
45#[cfg(test)]
46mod tests {}
haar_lib/algo/lis.rs

haar_lib/algo/
lis.rs
