Function leetcode_for_rust::cd0300_longest_increasing_subsequence::length_of_lis

pub fn length_of_lis(nums: Vec<i32>) -> i32

Solutions

Approach 1: Dynamic Programming

• Time complexity: O(nlogn)

• Space complexity: O(n)

• Runtime: 0 ms

• Memory: 2.5 MB

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        if nums.len() <= 1 { return nums.len() as i32; }

        let mut lis = vec![];
        lis.push(nums[0]);

        for i in 1..nums.len() {
            match lis.binary_search(&nums[i]) {
                Ok(n) => (),
                Err(n) => {
                    if n >= lis.len() { lis.push(nums[i]); } else { lis[n] = nums[i]; }
                },
            }
        }
        lis.len() as i32
    }
}

Approach 2: Dynamic Programming

• Time complexity: O(n2)

• Space complexity: O(n)

• Runtime: 12 ms

• Memory: 2.5 MB

use std::cmp::max;

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        if nums.len() <= 1 { return nums.len() as i32; }

        let mut dp = vec![1; nums.len()];
        let mut max_lis = 1;

        for i in 1..nums.len() {
            let mut tmp_max = 0;
            for j in 0..i {
                if nums[i] > nums[j] {
                    tmp_max = max(tmp_max, dp[j]);
                }
                dp[i] = tmp_max + 1;
            }
            max_lis = max(max_lis, dp[i]);
        }
        max_lis
    }
}

Approach 3: Dynamic Programming

• Time complexity: O(n2)

• Space complexity: O(n)

• Runtime: 8 ms

• Memory: 2.5 MB

use std::cmp::max;

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        if nums.len() <= 1 { return nums.len() as i32; }

        let mut dp = vec![1; nums.len()];
        let mut max_lis = 1;

        for i in 1..nums.len() {
            for j in 0..i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_lis = max(max_lis, dp[i]);
        }
        max_lis
    }
}