We solved this problem with Dynamic Programming in $O(n^2)$, but you can solve it faster with a single pass.

The best way to show you this is with an example. Say we have this array:

We want to do a single single pass to solve this problem, so we'll eventually get to some element like this one:

At this point, we've seen the increasing subsequences [1,3,4] and [1,2]. We need to somehow remember these subsequences, because we're doing a single pass and are not allowed to go backwards.

The trick to doing this efficiently is to combine all of the increasing subsequences we've seen into a single Array. We'll call it the combined array. The array will contain the smallest values in each of the subsequences, going element-by-element. Here's an example of this:

The solution to the problem is the length of the combined array.

To code this up, you loop through the given array arr, and slowly add elements to the combined array.

If the current element is greater than any of the elements in the combined array, you append it. Otherwise, you swap it into the combined array. To do this, you can use a binary search to figure out where to write the new element. This works because the combined array is always sorted. Here's the code for this:

Time Complexity $O(n \log n)$. We step through $n$ elements, and every time we step we do a Binary Search using biesct_left which takes $\log n$.

Space Complexity $O(n)$ to store the array.

You can also write your own code for the bisect_left function. See spoiler below.