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.
Recurrence Relation: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
For each element, we look at all previous elements that are smaller and extend the longest subsequence ending at that element.
Optimization: This can be solved in O(n log n) using binary search with a patience sorting approach, but the O(n^2) DP solution is the foundation.
nums = [10,9,2,5,3,7,101,18]4nums = [0,1,0,3,2,3]4nums = [7,7,7,7,7,7,7]11 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4Click "Run" to execute your code against test cases
Socratic guidance - I'll ask questions, not give answers