fn() longestIncreasingSubsequenceComputes the longest increasing subsequence.
Computes the longest increasing subsequence.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void longestIncreasingSubsequence(str, pos);
|
Parameters
str
|
An arbitrary ContainerConcept object. |
---|---|
pos
|
A String with the positions that belong to the longest increasing subsequence. |
Detailed Description
Remarks
The last position in pos indicates the first element in the longets increasing subsequence.
Example
#include <iostream> #include <seqan/graph_algorithms.h> using namespace seqan; int main() { // Create a sequence of integers. String<unsigned> seq; appendValue(seq, 5); appendValue(seq, 3); appendValue(seq, 4); appendValue(seq, 9); appendValue(seq, 6); appendValue(seq, 2); appendValue(seq, 1); appendValue(seq, 8); appendValue(seq, 7); appendValue(seq, 10); // Compute the longest increasing subsequence. typedef Position<String<unsigned> >::Type TPosition; String<TPosition> pos; longestIncreasingSubsequence(seq, pos); // Print the result to stdout. for (unsigned i = 0; i < length(seq); ++i) std::cout << seq[i] << ','; std::cout << "\n" << "Lis: \n"; for (int i = length(pos) - 1; i >= 0; --i) std::cout << seq[pos[i]] << ','; std::cout << "\n"; return 0; }
5,3,4,9,6,2,1,8,7,10, Lis: 3,4,6,7,10,
Data Races
Thread safety unknown!