Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is actually the length of one of the longest increasing subsequences. I need to this because I have to prove the greedy algorithm for finding all the decreasing subsequences having as few subsequences as possible. I have no idea of where to start, any help is much appreciated.
Edit: The big, greedy problem sounds like this: decompose the sequence in a minimum number of decreasing subsequences (non-strictly). Those are the subsequences I am talking about.