# Discussion on: Daily Coding Challenge #22 Idan Arye

My `O(n log n)` solution to the first problem: play.rust-lang.org/?version=stable...

``````fn length_of_lis(numbers: &[isize]) -> usize {
// This is the longest increasing subsequence that can end with a number:
let mut chain_length = std::collections::BTreeMap::new();

// This acts as a reverse index of chain_length. Since we always increase the length by one -
// it can be a vector:
let mut best_for_length = Vec::new();

for &num in numbers {
// Find the longest subsequence num can continue:
let continue_from = chain_length.range(..num).next_back();
let prefix_length = if let Some((_, &prefix_length)) = continue_from {
prefix_length
} else {
0
};

if prefix_length < best_for_length.len() {
// This is where the magic happens. If we already have a subsequence with the same
// length that ends with a higher number, we don't need that subsequence since any
// subsequence that can continue it can also continue this new subsequence we just
// discovered. By removing the old one, we are preventing the `continue_from` search
// from yielding a higher that represents a shorter subsequence.

let prev_best = best_for_length[prefix_length];
assert!(num <= prev_best); // otherwise num would have continued the subsequence
best_for_length[prefix_length] = num;
chain_length.remove(&prev_best);
} else {
best_for_length.push(num);
}
chain_length.insert(num, prefix_length + 1);
}
chain_length.values().max().copied().unwrap_or(0)

}
``````  