Find minimum number of Increasing subsequences.

Notice that given a division of the array into strictly increasing subsequences, it is always possible to make the endpoints of these subsequences decreasing (not strictly).

Why? well, if we have a subsequence $s_i$ whose endpoint is smaller than the endpoint of any of the following subsequences $s_j$ (with $i < j)$, we can assign the endpoint of $s_j$ to $s_i$. By applying this reasoning as many times as desired we can conclude that indeed, given a partition of the initial array into strictly increasing subsequences, it is possible to obtain a new partition with at most the same amount of subsequences, and such that the endpoints are decreasing.

Is it clear that if $d$ is the length of the longest decreasing subsequence, we will not be able to obtain a partition of the array in less than $d$ strictly increasing subsequences.

Furthermore, using what we just proved, we can see that we can always make a partition with at most $d$ increasing subsequences. Given an initial partition, and applying the aforementioned process, we can always obtain a partition of the array such that the endpoints are decreasing. However, as the longest decreasing subsequence has length $d$, it is not possible that this partition has more than $d$ subsequences, since the endpoints would form a decreasing subsequence of length more than $d$.

Hence the solution is exactly the length of longest decreasing subsequence.

Proof pasted from USACO guide:

Motivation: Consider the obvious greedy strategy to construct the collection of increasing subsequences (essentially patience sorting). For each element x of A from left to right, add it to the increasing subsequence with last element less than x such that the value of this last element is maximized. If no such increasing subsequence currently exists, then start a new increasing subsequence with x. This algorithm performs exactly the same steps as the algorithm to compute the length of the longest non-increasing subsequence, so it follows that they return the same result.

Proof: Let f[i] denote the length of longest non-increasing subsequence ending at A[i]. Then the A[i]'s satisfying f[i] for a fixed t are an increasing subsequence for each t. So we have covered A with (size of longest non-increasing subsequence) increasing subsequences, done.

Do you see why this is equivalent to the sketch?

Alternative Proof: This is just a special case of Dilworth's Theorem. See the inductive proof.