Source: https://leetcode.com/problems/longest-increasing-subsequence/

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].

/**
* @param {number[]} nums
* @return {number}
*/
// Brute Force Recursion
// We will keep track of the max of either taking or not taking the current number to be part of the longest increasing subsequence (lis)
// We can only take when the current number is greater than the previous number we took
// O(2^N) time, O(N) space and max recursion stack
var lengthOfLIS = function(nums) {
 function lisRecursive(i, prev) {
   // Base Case: When we can't pick anymore numbers
   if (i >= nums.length) {
     return 0;
   }
   
   // Recursively don't take this current number
   let dontTakeLis = lisRecursive(i + 1, prev);
   
   // Recursively take this current number if it's greater than the previous one
   let takeLis = 0;
   if (nums[i] > prev) {
     takeLis = 1 + lisRecursive(i + 1, nums[i]);
   }
   
   // Return whichever is larger from the recursive paths of taking or not taking the current valid number
   return Math.max(takeLis, dontTakeLis);
 }
 
 return lisRecursive(0, -Infinity);
};