competitive/combinatorial_optimization/
longest_increasing_subsequence.rs

1#[derive(Debug, Clone)]
2pub struct LongestIncreasingSubsequence<T> {
3    pub dp: Vec<T>,
4}
5
6impl<T> Default for LongestIncreasingSubsequence<T> {
7    fn default() -> Self {
8        Self { dp: Vec::new() }
9    }
10}
11
12impl<T> LongestIncreasingSubsequence<T> {
13    pub fn new() -> Self {
14        Default::default()
15    }
16    pub fn longest_length(&self) -> usize {
17        self.dp.len()
18    }
19}
20
21impl<T> LongestIncreasingSubsequence<T>
22where
23    T: Ord,
24{
25    pub fn insert(&mut self, x: T) {
26        let i = self.dp.binary_search(&x).unwrap_or_else(|x| x);
27        if let Some(t) = self.dp.get_mut(i) {
28            *t = x;
29        } else {
30            self.dp.push(x);
31        }
32    }
33}
34
35impl<T> Extend<T> for LongestIncreasingSubsequence<T>
36where
37    T: Ord,
38{
39    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
40        for x in iter.into_iter() {
41            self.insert(x);
42        }
43    }
44}