Isn't it a longest increasing subsrquence? I'm not sure if I understood the statement right — one will use a boat if all people that have used a boat until now are shorter than him. Did I get it right?

Hello ramprakash_k ,

This problem is just a modification of longest increasing subsequence problem as mentioned by @P_Nyagolov but in this case we need M such sequence disjoint sequences which maximise the total number of selected elements.

This problem can be solved using greedy approach. First select the longest increasing sequence of maximum length and assign this to M1. Remove all those elements which are selected in this LIS from the given permutation and then do the same process again. This way you will end up finding the maximum number of elements that are selected.

if dynammic programming is used to find the LIS then it will take O(M*N²) time. Otherwise, if data structure is used to find the LIS complexity boils down to O(M*Nlog(N)).

If you find anything incorrect then please reply back.

Ignore. The solution presented here was incorrect.

The length of longest decreasing sub-sequence gives you the minimum number of ships required to make all people board some ship.

so the problem is reduced to remove minimum number of elements in the permutation in order to make the length of longest decreasing sub-sequence no more than the number of ships you have , try to solve this one using dynamic programming

I decided to google this problem :) Here msg555 said that it can be solved with RSK algorithm. I haven't heard about this algorithm before; I've found few articles like this one, but I'm still not sure, will the answer to your question be equal to size of first M rows of generated tableaux (this makes some sense and works for random small cases), or we have to do some more complicated stuff :) Probably we should wait for someone more competent in it to provide correct solution, but now at least you have some key words for search :)

I_love_Tanya_Romanova is correct when he suggests that the RSK algorithm can be used to solve this problem. The number of cells in the first k rows in the generated Tableau equals the maximum cardinality of k disjoint increasing subsequences over the input permutation. The RSK tableau can be calculated completely in O(n^2) or the first k rows in O(nk log n). Using some symmetries you can actually compute the whole tableau in O(n^(3/2) log n) time.

To give a bit of the background, the RSK algorithm was thought up to facilitate a combinatorial proof relating the number of these (standard young) tableau to the number of permutations (it turns out there is a bijection between pairs of tableau of the same size and permutations). You can find the original proof of the theorem relating maximal cardinality of k increasing subsequences to RSK tableau at An Extension of Schensted's Algorithm.

On the average (i.e. for a random permutation) case the RSK algorithm already performs around O(n^(3/2)) time. However a long decreasing permutation, for example, takes O(n^2) time. To deal with this it's enough to observer the following. Let P(pi) give the result tableau for the permutation pi; then the following identity exists

P(pi) = P(reverse(pi))'

Where the apostrophe indicates an operation analogous to the transpose of matricies (exchanging columns and rows). Using this identity we can reconstruct P(pi) by computing the first sqrt(n) rows of P(pi) and the first sqrt(n) rows of P(reverse(pi)) and combining. Since the number of columns in each row of a tableau is non-increasing it follows that no cell can have a row and column index > sqrt(n). This lets us compute P(pi) in O(n^(3/2) log n).