c++ - シーケンス内の異なる項目の最長連続サブシーケンスを見つける

Question

配列内の異なる (!) 要素の最長の行をどのように見つけますか?

行列があります。私たちのタスクは、この行列の中で、異なる要素の最も長い行を見つけることです。

たとえば、0 1 2 3 4 1 2 3 カウントする必要があります 0 1 2 3 4 = 5 要素

Answer 1

ここで説明されている Kadane のアルゴリズムを使用してみてください: Maximum Subarray Problem

合計操作をセットへの追加操作とセット内検索操作に置き換えるだけです。したがって、O(n) アルゴを作成できます。

これは私の試みです：

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int mas[] = {1,2,3,1,2,3,4,1,2};
    size_t count = sizeof(mas)/sizeof(mas[0]);

    size_t best = 0;
    int best_index = 0;
    unordered_set<int> unique;
    for (int i = 0; i < count; i++) {
        while (unique.find(mas[i]) != unique.end()) {
            unique.erase(mas[i - unique.size()]);
        }
        unique.insert(mas[i]);
        if (unique.size() > best) {
            best = unique.size();
            best_index = i - best + 1;
        }
    }

    cout << "Index = " << best_index << " Length = " << best << endl;
}

出力を与えます：

Index = 3 Length = 4