Skip to content

Instantly share code, notes, and snippets.

@zoeisnowooze
Created February 21, 2022 22:02
Show Gist options
  • Save zoeisnowooze/3932eae663f649c66b9e377cc6e05c9b to your computer and use it in GitHub Desktop.
Save zoeisnowooze/3932eae663f649c66b9e377cc6e05c9b to your computer and use it in GitHub Desktop.
longest-sub-seq
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
);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment