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));
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.