fn() heaviestIncreasingSubsequence
Computes the heaviest increasing subseqnece.

Defined in <seqan/graph_algorithms.h>
Signature void heaviestIncreasingSubsequence(str, weights, pos);

Parameters

str An arbitrary ContainerConcept object.
weights A String with a weight for each position in the string.
pos A String with positions that indicate the members of the heaviest increasing subsequence.

Detailed Description

Remarks

The last position in pos indicates the first member of the heviest increasing subsequence. Note that only members that contribute a weight are selected, that is, positions with associated 0 weights are ignored.

Example

#include <iostream>
#include <seqan/sequence.h>
#include <seqan/graph_algorithms.h>

using namespace seqan;

int main()
{
    // Fill a string and define corresponding weights.
    String<char> seq("zeitgeist");
    String<unsigned int> weights;
    resize(weights, length(seq), 1);
    assignProperty(weights, 2, 10);

    // Compute heaviest increasing subsequence.
    typedef Position<String<unsigned int> >::Type TPosition;
    String<TPosition> pos;
    unsigned int w = heaviestIncreasingSubsequence(seq, weights, pos);

    // Print the results to stdout.
    for (int i = 0; i < (int) length(seq); ++i)
        std::cout << seq[i] << "(Weight=" << getProperty(weights, i) << "),";
    std::cout << "\n"
              << "His: \n";
    for (int i = length(pos) - 1; i >= 0; --i)
        std::cout << seq[pos[i]] <<  ',';
    std::cout << "(Weight=" << w << ")\n";

    return 0;
}
z(Weight=1),e(Weight=1),i(Weight=10),t(Weight=1),g(Weight=1),e(Weight=1),i(Weight=1),s(Weight=1),t(Weight=1),
His:
e,i,s,t,(Weight=13)

Data Races

Thread safety unknown!

See Also