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.

Improve this question
$\endgroup$
8
  • $\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. ♦
    Commented Nov 23, 2016 at 19:22
  • 1
    $\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
    Commented Nov 23, 2016 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
    Commented Nov 23, 2016 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
    Commented Nov 23, 2016 at 20:03
  • 1
    $\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
    Commented Nov 23, 2016 at 20:07

1 Answer 1

Reset to default
3
$\begingroup$

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 > 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 "patience sort" algorithm?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.