z-rna

RNA (ribonucleic acid) is very important molecular structure which participates in the vital processes of the cells, especially in multiplying of DNA. It organizes the whole process of replication of DNA (deoxyribonucleic acid).

RNA represents a polynucleotid combined of the following nucleotids: A (adenine), G (guanine), U (uracil) and C (cytosine). It's also known that A and U, C and G , G and U form additional chemical links. That means the links are possible A - U , U - A, C – G, G – C, G – U и U – G.

To determine twodimensional structure of this complexed molecule it's required to determine the additional chemical links between the nucleotides. One of the simplest predictions of these links is to maximize the number of these links, while the rule remains that two neighbour nucleotides must not form a link.

The molecule of RNA is represented as an array of the above mentioned nucleotides. Your task is to write a program for a given array of nucleotides to maximize the number of these additional links.

For example, let the string which represents the RNA sequence be
AUGAAAGUCUAAGUACUUUAGCGGGACCGGGCCUAA

Then the maximal number of additional links that can be made is 14. The folding looks like this: