[boost] [algorithm] Interface for longest_increasing_subsequence (proposal)

Hi all, I want to propose a new algorithm to Boost.Algorithm: a well-known longest increasing subsequence https://en.wikipedia.org/wiki/Longest_increasing_subsequence (LIS for short). Just for a short info: given a sequence like ( 7 )( 2 )( 8 )( 1 )( 3 )( 4 )( 10 )( 6 )( 9 )( 5 ), the result will be a subsequence ( 1 )( 3 )( 4 )( 6 )( 9 ). The proposed algorithm has O(n log n) time and O(n) complexity, where n - sequence length. I have created a pull request https://github.com/boostorg/algorithm/pull/7. I have however some questions. I am not sure what should be the exposed interface. For the moment, I propose (I base it on the existing interface from algorithm/searching functions): - class longest_increasing_subsequence with methods - operator() - *compute_length* (a better name may be needed) - free function longest_increasing_subsequence_length returning the length of the LIS and taking as arguments: - a pair of iterators (first, last) - or a range - and (optionally) a comparison predicate - *free function longest_increasing_subsequence_search taking the same arguments as _length function and an Output Iterator or a tag.* - free function make_longest_increasing_subsequence taking a range and optionally a comparison predicate and returning corresponding longest_increasing_subsequence object The problematic part is the underlined longest_increasing_subsequence_search function and the way in which I should return the resulting LIS. I see possibilities like the following: 1. taking an OutputIterator argument: the best for me, generic and the most flexible solution, but there is a performance hit as we cannot reserve the memory for the output LIS. 2. returning a container with the subsequence, e.g. std::vector: no performance hit with small objects or if the user needs a vector of values. However, not really generic as the user would be obliged to use a vector (in the aforementioned example). 3. returning a container with iterators, e.g. std::vector<InputIter>: good if a container of iterators is acceptable, it has a benefit of avoiding possibly expensive copies of sequence elements. As 2., not really generic. 4. -taking a container as an argument: the worst solution in my eyes, there is no way nice way to write generic code that handles all containers. I have coded possibilities 1-3. Thank you in advance for all the comments, corrections etc. Regards, Marek Kurdej