Given an integer array nums, return the length of the longest strictly increasing subsequence — elements don't need to be contiguous, just in increasing order and appearing in their original relative order.
Example
Input nums = [10,9,2,5,3,7,101,18]
Output 4
Key Pointers
dp[i] = length of the longest increasing subsequence ending exactly at index i; the final answer is the max over all dp[i], not just dp[-1].
dp[i] = 1 + max(dp[j] for every j < i where nums[j] < nums[i]), or just 1 if no such j exists.
This O(n²) version is the one worth internalizing first — a faster O(n log n) patience-sorting approach exists, but it builds on the same recurrence idea.
Step-by-Step Analysis
Initialize dp as an array of 1s (every element is, at minimum, a subsequence of length 1 on its own).
For each index i from 1 to n−1: for each earlier index j from 0 to i−1, if nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).
Track the running maximum of dp as it's computed, or take max(dp) once the loops finish.
Return that maximum.
Complexity
Time: O(n²) — Space: O(n)
Code
def lengthOfLIS(nums: list[int]) -> int:
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Code Explanation
How the solution above works, piece by piece.
dp[i] = length of the longest increasing subsequence that ends with nums[i]. Every element alone gives 1.
For each earlier j with nums[j] < nums[i], nums[i] can extend that chain: dp[j] + 1.
Keep the best such extension.
The answer is the largest dp value, since the longest chain can end anywhere.
O(n²) time, O(n) space (a binary-search version gets O(n log n)).
Visual Walkthrough
Running it on nums = [10, 9, 2, 5, 3, 7, 101, 18]:
Each dp[i] looks back at every smaller earlier number and extends the best chain ending there. 101 and 18 both end chains of length 4 (2, 3, 7 then 101 or 18), so the answer is 4.