c++ - C++中的最大子序列

问题:

我的代码中的错误在哪里？

问题:

我想在字符串中找到最大的唯一子序列。示例:对于aabbaba，答案将为2(ab或ba)。我想通过只重复一次字符串来做到这一点。只允许使用小写字母。

正如@hvd所指出的，如果子序列中的所有字母都是唯一的，则它是唯一的。字符串中可能多次出现相同的唯一子序列。

方法:

从字符串的第一个字母开始，然后迭代结束

如果尚未看到字母

，请在 vector unique中写出字母出现的位置

增加此子序列的计数

如果您看到字母，请开始一个新的子序列。使用从当前位置到最后一个位置的距离来初始化新的子序列。示例:字符串是exampletzu。我们处于第二个e。当前索引为6。当前最大子序列为6(exampl)。转到t并创建一个新的子序列。将其初始化为7(xamplet)。

您知道如果当前子序列等于26，则可以中止，因为那是

的最大可能值

代码:

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    int length = 7;
    string p = "aabbaba";
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
                    unique[j] = unique[pos];
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }

最佳答案

更新unique时，应保留unique[pos]以后已经出现的字母:

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    p = argv[1];
    length = p.length();
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
          if (unique[j] < unique[pos]) {
                    unique[j] = unique[pos];
          }
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }

关于c++ - C++中的最大子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50446885/