LeetCode 300 Longest Increasing Subsequence - Implementation

Here's the full solution:

function lengthOfLIS(nums)
    n := length of nums
    dp := array of size n, all set to 1
    for i from 1 to n - 1
        for j from 0 to i - 1
            if nums[j] < nums[i]
                dp[i] := max(dp[i], dp[j] + 1)
    maxLen := 0
    for i from 0 to n - 1
        maxLen := max(maxLen, dp[i])
    return maxLen

Time: $O(n^2)$. Space: $O(n)$.

For each position $i$, you check all earlier positions $j$. If nums[j] < nums[i], you can extend that subsequence. You take the best extension.

This is the classic DP approach. It's correct but slow for large inputs. The binary search version runs in $O(n \log n)$.