LeetCode 300: Longest Increasing Subsequence — Step-by-Step Visual Trace

Medium — Dynamic Programming | Array | Binary Search The Problem Find the length of the longest strictly increasing subsequence in an array of integers. A subsequence maintains the relative order of elements but doesn't need to be contiguous. Approach Use dynamic programming where dp[i] represents the length of the longest increasing subsequence ending at index i. For each element, check all previous elements and extend their subsequences if the current element is larger. Time: O(n²) · Space: O(n) Code class Solution : def lengthOfLIS ( self , nums : List [ int ]) -> int : if not nums : return 0 # Initialize a dynamic programming array dp with all values set to 1. dp = [ 1 ] * len ( nums ) # Iterate through the array to find the longest increasing subsequence. for i in range ( len ( nums )): for j in range ( i ): if nums [ i ] > nums [ j ]: dp [ i ] = max ( dp [ i ], dp [ j ] + 1 ) # Return the maximum value in dp, which represents the length of the longest increasing subsequence. retu