LeetCode 300 Longest Increasing Subsequence - Example and Complexity Analysis

Trace nums = [10,9,2,5,3,7,101].

dp[0] = 1 (just [10]) dp[1] = 1 (just [9], no smaller before it) dp[2] = 1 (just [2]) dp[3] = dp[2] + 1 = 2 ([2,5]) dp[4] = dp[2] + 1 = 2 ([2,3]) dp[5] = max(dp[3], dp[4]) + 1 = 3 ([2,5,7] or [2,3,7]) dp[6] = dp[5] + 1 = 4 ([2,5,7,101])

Answer: $4$.

$O(n^2)$ time (nested loops). $O(n)$ space. A binary search optimization achieves $O(n \log n)$.