# Find minimum number of Increasing subsequences.

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.

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$$.