Leetcode 300 - Longest Increasing Subsequence

Prompt: Given an integer array, return the length of the longest increasing subsequence.

Example:

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.

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

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Solution: We can solve this with bottom up tabulation. First, we can loop through each integer and decide the past max length before the current integer. Then, we can have an inner loop that loops from the start to the current integer and pick the max length from those integers that are less than the current integer. Finally, we can add 1 to the past max length. The runtime for this solution is O(n²) since we have a 2 level nested loop.