Challenge 45

Longest Increasing Subsequence

You are given an array of integers nums, find the length of the longest increasing subsequence. A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Solution

#![allow(unused)]

fn main() {
pub fn longest_increasing_subsequence(nums: Vec<i32>) -> usize {
    if nums.is_empty() {
        return 0;
    }

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

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

    max_len
}
}