def length_of_lis(nums):
n = len(nums)
if n == 0:
return 0
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Variables
n- length of the input array nums
Explanation
Two nested loops over the array - **O(n²)** time. The DP array is **O(n)** space. There is an O(n log n) variant using binary search on a tails array; this O(n²) form is the textbook canonical.