1
$\begingroup$

Problem:

Given an array of integers of size N, divide it into the minimum number of “strictly increasing subsequences”

Solution:

This is a well know problem and the solution is the length of longest decreasing subsequence.

I am looking for a proof for this.

$\endgroup$
2
$\begingroup$

Notice that given a division of the array into strictly increasing subsequences, it is always possible to make the endpoints of these subsequences decreasing (not strictly).

Why? well, if we have a subsequence $s_i$ whose endpoint is smaller than the endpoint of any of the following subsequences $s_j$ (with $i < j)$, we can assign the endpoint of $s_j$ to $s_i$. By applying this reasoning as many times as desired we can conclude that indeed, given a partition of the initial array into strictly increasing subsequences, it is possible to obtain a new partition with at most the same amount of subsequences, and such that the endpoints are decreasing.

Is it clear that if $d$ is the length of the longest decreasing subsequence, we will not be able to obtain a partition of the array in less than $d$ strictly increasing subsequences.

Furthermore, using what we just proved, we can see that we can always make a partition with at most $d$ increasing subsequences. Given an initial partition, and applying the aforementioned process, we can always obtain a partition of the array such that the endpoints are decreasing. However, as the longest decreasing subsequence has length $d$, it is not possible that this partition has more than $d$ subsequences, since the endpoints would form a decreasing subsequence of length more than $d$.

Hence the solution is exactly the length of longest decreasing subsequence.

$\endgroup$
0

Your Answer

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

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