longestIncreasingSubsequence

Calculate a longest increasing subsequence of sequence. This subsequence is not necessarily contiguous, or unique. Given a sequence of n elements the algorithm uses O(n log n) evaluation of pred.

longestIncreasingSubsequence
(
alias pred = "a < b"
Range
)
(
Range sequence
)
if (
isRandomAccessRange!Range
)

Examples

Example from Wikipedia

1 import std.algorithm : equal;
2 
3 auto inputSequence = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
4 auto expectedOutput = [0, 2, 6, 9, 11, 15];
5 
6 assert(inputSequence.longestIncreasingSubsequence.equal(expectedOutput));

Example using a different pred

1 import std.algorithm : equal;
2 import std.range : retro;
3 
4 auto inputSequence = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
5 auto expectedOutput = [12, 10, 9, 5, 3];
6 
7 assert(inputSequence.longestIncreasingSubsequence!"a > b".equal(expectedOutput));

See Also

Meta