Basically what you are asking is the minimum number of chains required to cover the whole array (a chain is an increasing sequence of numbers), which, by dilworth's theorem is equal to the length of the longest decreasing subsequence of the array. Finding the LDS, is just the opposite of finding the LIS (a standard DP problem).