use std::cmp::Ordering;

fn heaviest_subseq(in_list: &[i32]) -> i32 {
    let mut best_subseq = vec![(0, 0)];

    for new_elem in in_list {
        let insert_loc = match best_subseq
            .binary_search_by(|&(key, _)| if key < *new_elem { Ordering::Less } else { Ordering::Greater })
        {
            Ok(index) => index,
            Err(index) => index,
        };

        let best_pred_subseq_val = best_subseq[insert_loc - 1].1;

        let new_subseq_val = new_elem + best_pred_subseq_val;

        let mut num_deleted = 0;

        while num_deleted + insert_loc < best_subseq.len() && best_subseq[insert_loc].1 <= new_subseq_val {
            best_subseq.remove(insert_loc);
            num_deleted += 1;
        }

        best_subseq.insert(insert_loc, (*new_elem, new_subseq_val));
    }

    best_subseq.into_iter().map(|(_, val)| val).max().unwrap()
}

fn main() {
    let tests = [
        &[][..],
        &[3][..],
        &[3, 2, 1][..],
        &[3, 2, 5, 6][..],
        &[9, 3, 2, 1, 4][..],
        &[3, 4, 1, 4, 1][..],
        &[9, 1, 2, 3, 4][..],
        &[1, 2, 4, 3, 4][..],
        &[9, 1, 2, 3, 4, 5, 10][..],
        &[3, 2, 1, 2, 3][..],
    ];

    for test in &tests {
        println!("{:?} {:?}", test, heaviest_subseq(test));
    }
}

use std::cmp::Ordering;

fn heaviest_subseq(in_list: &[i32]) -> i32 {
    let mut best_subseq = vec![(0, 0)];

    for new_elem in in_list {
        let insert_loc = match best_subseq
            .binary_search_by(|&(key, _)| if key < *new_elem { Ordering::Less } else { Ordering::Greater })
        {
            Ok(index) => index,
            Err(index) => index,
        };

        let best_pred_subseq_val = best_subseq[insert_loc - 1].1;

        let new_subseq_val = new_elem + best_pred_subseq_val;

        let mut num_deleted = 0;

        while num_deleted + insert_loc < best_subseq.len() && best_subseq[insert_loc].1 <= new_subseq_val {
            best_subseq.remove(insert_loc);
            num_deleted += 1;
        }

        best_subseq.insert(insert_loc, (*new_elem, new_subseq_val));
    }

    best_subseq.into_iter().map(|(_, val)| val).max().unwrap()
}

fn main() {
    let tests = [
        &[][..],
        &[3][..],
        &[3, 2, 1][..],
        &[3, 2, 5, 6][..],
        &[9, 3, 2, 1, 4][..],
        &[3, 4, 1, 4, 1][..],
        &[9, 1, 2, 3, 4][..],
        &[1, 2, 4, 3, 4][..],
        &[9, 1, 2, 3, 4, 5, 10][..],
        &[3, 2, 1, 2, 3][..],
    ];

    for test in &tests {
        println!("{:?} {:?}", test, heaviest_subseq(test));
    }
}