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!