Proof that the length of the largest ascending subsequence is the number of decreasing subsequences
You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of subsequences (piles) is minimal.
To prove that, we need to consider two things.
Claim 1: the length of the LIS is a lower bound on the number of piles. That follows from the fact that each of the elements in the LIS must go into a different pile, for if any two elements end up in the same pile, it would no longer be nonincreasing.
Claim 2: the number of piles obtained by Patience Sorting is a lower bound on the length of the LIS. Wikipedia has a proof. To summarize: whenever we place a card C in pile X &gt; 1, we add a pointer from card C to the current top card at pile X - 1 (which is necessarily smaller). If we end up with N piles, we can start at the card on top of pile N, and follow back pointers to construct a strictly increasing subsequence of length N (in reverse).
Combine 1 and 2 to conclude that the length of the LIS is equal to the minimum number of nondecreasing subsequences in the partition (and such a partition is produced by Patience Sorting).
If this is still unclear, there is a similar question about Patience Sort here:
How to prove the optimality of the &quot;patience sort&quot; algorithm?