# Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

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.

Thank you.

• Welcome to CS.SE! What have you tried? Have you worked through a few examples, and tried to look for any patterns that might be useful? Have you checked carefully whether this is indeed true, by working through some examples? I don't think that it is true. We're happy to help you understand concepts, but just solving an exercise problem for you is unlikely to achieve that. You might find the following helpful: meta.cs.stackexchange.com/q/1284/755
– D.W.
Commented Nov 23, 2016 at 19:22
• Is there something you are leaving out? The statement you are stating isn't provable because it isn't true. Here is an example 5,1,2,6,7,8. There are 2 decreasing sub sequences 5,1 and 5,2. The longest increasing subsequence is: 1,2,6,7,8 Commented Nov 23, 2016 at 19:41
• @IPlant It is true in this case: the decreasing subsequences will be: [5, 1] , [2] , [6], [7], [8] , so 5 dereasing subsequences which is also the length of [1, 2, 6, 7, 8] Commented Nov 23, 2016 at 19:55
• so to clarify the question again, it is maximal decreasing sub-sequences, which you need to state in your question as well. Otherwise [5] [1] [2] [6] [7] [8] [5,1] [5,2] are all decreasing sub sequences and there 8 of them Commented Nov 23, 2016 at 20:03
• @IPlant : Yes, I didn't realize I didn't mention. The big problem I have to solve sounds like this: decompose the sequence in a minimum number of decreasing subsequences (non-strictly). Those are the subsequences I am talking about. Commented Nov 23, 2016 at 20:07