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.