Problem statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Link to problem

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

Solutions

Approach 1: Dynamic Programming

There is perhaps no problem worse than this one (inb4 it keeps getting worse from here on).
I’ve spent about a day pondering about it and couldn’t find a solution, I had to go look at LeetCode solutions, only to realize that I still didn’t understand anything at all.

Surprisingly, a GeeksForGeeks video1 helped me understand how to solve this god forsaken problem.

The idea behind it is quite simple, you initialize an array dp of size N with 1 and iteratively check whether the previous number is smaller, if it is, then you increment dp AND also check if current dp is less than previous dp + 1.

Pseudocode

initialize array dp of size N with 1s
max = 0

begin ith loop from 1 to N - 1
    begin jth loop from 0 to i - 1
        if dp[i] > dp[j] AND dp[i] < dp[j] + 1
            dp[i] = dp[j] + 1
    
    get max of max and dp[i]

return max

Implementation in Rust

fn length_of_lis(nums: Vec<i32>) -> i32 {
    let mut max_count: i32 = 0;
    let mut dp = vec![1; nums.len()];
    if nums.len() == 1 {
        return 1;
    }
    for i in 1..nums.len() {
        for j in 0..i {
            if nums[i] > nums[j] && dp[i] < dp[j] + 1{
                dp[i] = dp[j] + 1;
            }
        }
        max_count = std::cmp::max(dp[i], max_count);
    }
    max_count
}

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
Runtime on LeetCode: $99$ms, wow.

There are more hair pulling approaches.
NeedCode2 covered three of those, including the one here.