41 lines
1.0 KiB
Plaintext
41 lines
1.0 KiB
Plaintext
fn lower_bound<T: PartialOrd>(list: &Vec<T>, value: &T) -> usize {
|
|
if list.is_empty() {
|
|
return 0;
|
|
}
|
|
let mut lower = 0usize;
|
|
let mut upper = list.len();
|
|
while lower != upper {
|
|
let middle = lower + upper >> 1;
|
|
if list[middle] < *value {
|
|
lower = middle + 1;
|
|
} else {
|
|
upper = middle;
|
|
}
|
|
}
|
|
return lower;
|
|
}
|
|
|
|
fn lis<T: PartialOrd + Copy>(list: &Vec<T>) -> Vec<T> {
|
|
if list.is_empty() {
|
|
return Vec::new();
|
|
}
|
|
let mut subseq: Vec<T> = Vec::new();
|
|
subseq.push(*list.first().unwrap());
|
|
for i in list[1..].iter() {
|
|
if *i <= *subseq.last().unwrap() {
|
|
let index = lower_bound(&subseq, i);
|
|
subseq[index] = *i;
|
|
} else {
|
|
subseq.push(*i);
|
|
}
|
|
}
|
|
return subseq;
|
|
}
|
|
|
|
fn main() {
|
|
let list = vec![3, 2, 6, 4, 5, 1];
|
|
println!("{:?}", lis(&list));
|
|
let list = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
|
|
println!("{:?}", lis(&list));
|
|
}
|