\(L_i=(A_1,A_2,\ldots,A_i)\) に含まれる整数の種類数

\(R_i=(A_i,A_{i+1},\ldots,A_N)\) に含まれる整数の種類数

とします。

このとき、答えは \(\max_{1 \leq i \leq N-1} (L_i+R_{i+1})\) となります。つまり、\(L,R\) をそれぞれ計算することができれば答えを求めることができます。

\(R\) は \(A\) を逆順にしたて \(L\) と同様の求め方をすればいいです。また、\(L\) は実際に高速に求めることが可能です。 以下の手順で求められます。

\(S=0,V=(0,0,0,0,\ldots,0) \) とします。このとき、\(V\) は長さ \(N\) の配列です。

\(i=1,2,\ldots,N\) の順に以下を行う

• \(V_{A_i}=0\) ならば、\(V_{A_i} \larr 1\) 、\(S \larr S+1\) とする。
• \(L_i \larr S\)

同様に\(R\) を求め、\(L,R\) から上で示した式を計算し、答えを計算できます。

時間計算量は \(O(N)\) です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &e : a)
        cin >> e;
    vector<int> suml(n), sumr(n);
    vector<int> vis(n + 1, 0);
    int now = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[a[i]]) {
            now++;
        }
        vis[a[i]] = 1;
        suml[i] = now;
    }
    now = 0;
    vis = vector<int>(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        if (!vis[a[i]]) {
            now++;
        }
        vis[a[i]] = 1;
        sumr[i] = now;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        ans = max(ans, suml[i] + sumr[i + 1]);
    }
    cout << ans << endl;
}