longest-sub-seq

main.rs

use std::env;
use std::ops::RangeInclusive;

trait RangeInclusiveExt {
    fn len(&self) -> usize;
}

impl RangeInclusiveExt for RangeInclusive<usize> {
    fn len(&self) -> usize {
        *self.end() - *self.start() + 1
    }
}

fn longest_sub_seq(seq: &[usize]) -> usize {
    let mut ranges: Vec<RangeInclusive<usize>> = vec![];
    for i in seq {
        let mut left: Option<RangeInclusive<usize>> = None;
        let mut right: Option<RangeInclusive<usize>> = None;
        let mut new_ranges: Vec<RangeInclusive<usize>> = vec![];
        for range in ranges.iter() {
            if *i == range.start() - 1 {
                right = Some(RangeInclusive::new(*i, *range.end()));
            } else if *i == range.end() + 1 {
                left = Some(RangeInclusive::new(*range.start(), *i));
            } else {
                new_ranges.push(range.clone());
            }
        }
        if let (Some(l), Some(r)) = (&left, &right) {
            new_ranges.push(RangeInclusive::new(*l.start(), *r.end()));
        } else if left.is_some() || right.is_some() {
            if let Some(l) = left {
                new_ranges.push(l);
            }
            if let Some(r) = right {
                new_ranges.push(r);
            }
        } else {
            new_ranges.push(RangeInclusive::new(*i, *i));
        }
        ranges = new_ranges;
    }
    ranges.iter().map(|range| range.len()).max().unwrap_or(0)
}

fn main() {
    let args: Vec<usize> = env::args()
        .skip(1)
        .map(|arg| str::parse(&arg).unwrap())
        .collect();
    println!("{}", longest_sub_seq(&args));
}

#[test]
fn test_sequences() {
    assert_eq!(longest_sub_seq(&[]), 0);
    assert_eq!(longest_sub_seq(&[1, 9, 87, 3, 10, 4, 20, 2, 45]), 4);
    assert_eq!(
        longest_sub_seq(&[36, 41, 56, 35, 91, 33, 34, 92, 43, 37, 42]),
        5
    );
}