loading...

Discussion on: Daily Coding Challenge #22

Collapse
idanarye profile image
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)

}