Longest Increasing Subsequence
Return the length of the longest strictly increasing subsequence. The elements don't have to be next to each other.
A way to picture it
Kids stand in a line for a photo, and you want the longest chain of kids, in line order, where each is taller than the one before. For each kid, look back at every shorter kid and ask: whose chain could I join to make mine as long as possible?
How to approach it
lis(i) = longest increasing subsequence ending at i = 1 + max lis(j) over earlier j with nums[j] < nums[i]. The answer is the largest lis(i).
Example
Input: {"nums":[10,9,2,5,3,7,101,18]}. Output: 4.
Complexity: O(n²) time and O(n) space. Each element looks back at every earlier one.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.