1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – D.W. Nov 23 '16 at 19:22
  • $\begingroup$ 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 $\endgroup$ – lPlant Nov 23 '16 at 19:41
  • $\begingroup$ @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] $\endgroup$ – Toma Radu-Petrescu Nov 23 '16 at 19:55
  • $\begingroup$ 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 $\endgroup$ – lPlant Nov 23 '16 at 20:03
  • $\begingroup$ @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. $\endgroup$ – Toma Radu-Petrescu Nov 23 '16 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.