Question

How to find the longest increasing not sorted subsequence (LIS) of a sequence of numbers in Rust

Answer 1

fn longest_increasing_subsequence(nums: &[i32]) -> usize {
    let numslen = nums.len();
    
    if numslen == 0 {
        return 0;
    }

    let mut length = vec![1; numslen];
    let mut max_length = 1;

    for i in 1..numslen {
        for j in 0..i {
            if nums[i] > nums[j] {
                length[i] = length[i].max(length[j] + 1);
            }
        }
        max_length = max_length.max(length[i]);
    }

    max_length
}

fn main() {
    let nums = vec![4, 5, 1, 10, 3, 9, 18, 19];
    
    let result = longest_increasing_subsequence(&nums);
    
    println!("Length of LIS: {}", result);
}



/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals