Leetcode Blind 75C++: Longest Increasing Subsequence

Hey Everyone, Im going over the Blind 75, so decided to make a series on them to help solidify concepts prior to interviews. Below I have attached my notes from doing questions and if have any other questions feel free to let me know!

Thank you

[GChief]

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// Input: Given an array `nums`.
// Step 1: Initialize an array `dp` of size `n` and fill it with 1.
int n = nums.size();
vector<int> dp(n, 1);

// What DSA/Algorithm to use: Dynamic Programming.
// Step 2: Loop over the array from the second number.
for(int i = 1; i < n; i++) {
// What to do with data
// Step 3: For each number, iterate over all previous numbers.
for(int j = 0; j < i; j++) {
// Step 4: If the current number is larger than a previous number, update dp for the current number to be the maximum of dp for the current number and dp of the previous number plus 1.
if(nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}

// Output: Return the maximum value in dp.
// Step 5: Return the maximum value in `dp`.
return *max_element(dp.begin(), dp.end());
}
};

Space and Time Complexity
Time: O(n^2)
Space: O(n)

[davidhallinen-lics]

it would help a lot if you also printed the array dp so that we can see how it's being filled what it's being filled with