One-dimensional Dynamic Programming
Best answer ending here
A quadratic table that is easy to derive, and a logarithmic trick that is worth knowing but not guessing.
Key idea
Ending here, not anywhere
The state that works is: the best answer among those that end at position i. Not the best over the whole prefix, which sounds simpler and does not compose.
The reason is the transition. To extend an answer with element i, you need to know that the previous element is compatible with i, and only an ending-here state tells you what the previous element was.
The final answer is then the maximum over all positions, taken at the end. Forgetting that last step and returning the value at the final position is a common slip.
Tip
This is a complete answer
The double loop is O(n squared) and it is derived directly from the state sentence. In an interview this is a good answer, and you should give it and state its cost before attempting anything faster.
The faster solution below is genuinely clever and is not something to derive under pressure if you have not seen it. Recognizing that is better judgment than gambling on it.
Key idea
The logarithmic version, and what it is really doing
Keep a list where position k holds the smallest possible value that can end an answer of length k plus one. That list is always sorted, which is what allows a binary search.
For each element, find the first entry that is not smaller than it and overwrite that entry. If no such entry exists, the element extends the list. The answer is the list's final length.
The list is not itself a valid answer, and that is the part that surprises people. Its length is correct; its contents are the best possible endings, not a reconstruction.
Gotcha
Which bisect depends on strictness
bisect_left treats an equal value as not extending, which is what a strictly increasing requirement needs. For a non-decreasing requirement, bisect_right is the correct one.
The two differ on exactly the inputs containing duplicates, so a run of identical values is the test that separates them: under the strict reading it gives an answer of 1, and under the other it gives the length of the run. Deciding which the problem wants and picking the matching function is the whole difference.
This is the U5 lesson about knowing which of the two you want, showing up somewhere it silently changes an answer.
Give the first, mention the second
Write the quadratic version, state that it is O(n squared), and say that an O(n log n) solution exists using a sorted list of best endings and a binary search.
If asked to implement it, it is the loop above with the two cases turned into an assignment and an append, and the answer is the list's final length. If not asked, you have already demonstrated that you know it exists, which is most of the credit.
Cost of the table version
Time and space for the quadratic longest-run version on n values.
Time
Space
Longest Increasing Subsequence
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.