Finding lengths of Longest Increasing Subsequence by its length with Rust.

lis.rs

pub fn longest_increasing_subsequence<T: Ord>(nums: impl IntoIterator<Item = T>) -> Vec<usize> {
    let mut nums = nums.into_iter();
    let Some(first) = nums.next() else {
        return vec![];
    };
    let mut len_by_using = vec![1];
    let mut sorted = vec![first];
    for num in nums {
        let lower_bound = sorted.binary_search(&num).unwrap_or_else(|idx| idx);
        if lower_bound == sorted.len() {
            sorted.push(num);
        } else {
            sorted[lower_bound] = num;
        }
        len_by_using.push(sorted.len());
    }
    len_by_using
}