algorithm - 元音子序列

Question

我在练习面试时在一个网站上遇到了这个问题:

A magical sub-sequence of a string S is a sub-sequence of S that contains all five vowels in order. Find the length of largest magical sub-sequence of a string S.

For example, if S = aeeiooua, then aeiou and aeeioou are magical sub-sequences but aeio and aeeioua are not.

我是动态规划的初学者，发现很难为此提出递归公式。

Answer 1

我用迭代方法而不是递归方法来完成它。我开始构建类似于 LIS(最长递增子序列)的解决方案，然后将其优化到 O(n)。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string vowel = "aeiou";

int vpos(char c)
{
    for (int i = 0; i < 5; ++i)
        if (c == vowel[i])
            return i;
    return -1;
}

int magical(string s)
{
    int l = s.length();
    int previndex[5] = {-1, -1, -1, -1, -1};    // for each vowel
    vector<int> len (l, 0);
    int i = 0, maxlen = 0;

    // finding first 'a'
    while (s[i] != 'a')
    {
        ++i;
        if (i == l)
            return 0;
    }

    previndex[0] = i;       //prev index of 'a'
    len[i] = 1;

    for ( ++i; i < l; ++i)
    {
        if (vpos(s[i]) >= 0)    // a vowel
        {
            /* Need to append to longest subsequence on its left, only for this vowel (for any vowels) and 
             * its previous vowel (if it is not 'a')
                This important observation makes it O(n) -- differnet from typical LIS
            */
            if (previndex[vpos(s[i])] >= 0)
                len[i] = 1+len[previndex[vpos(s[i])]];

            previndex[vpos(s[i])] = i;

            if (s[i] != 'a')
            {
                if (previndex[vpos(s[i])-1] >= 0)
                    len[i] = max(len[i], 1+len[previndex[vpos(s[i])-1]]);
            }

            maxlen = max(maxlen, len[i]);
        }
    }
    return maxlen;
}

int main()
{
    string s = "aaejkioou";
    cout << magical(s);
    return 0;
}