Find minimum number of Increasing subsequences. Problem:
Given an array of integers of size N, divide it into the minimum number of “strictly increasing subsequences”
Solution:
This is a well know problem and the solution is the length of longest decreasing subsequence.
I am looking for a proof for this.
 A: 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.
A: 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.
