Submission #63839456

---

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Precompute prefix distinct counts
    vector<int> prefixDistinct(N);
    unordered_set<int> prefixSet;
    for (int i = 0; i < N; ++i) {
        prefixSet.insert(A[i]);
        prefixDistinct[i] = prefixSet.size();
    }

    // Precompute suffix distinct counts
    vector<int> suffixDistinct(N);
    unordered_set<int> suffixSet;
    for (int i = N - 1; i >= 0; --i) {
        suffixSet.insert(A[i]);
        suffixDistinct[i] = suffixSet.size();
    }

    // Calculate the maximum sum of prefix and suffix distinct counts
    int maxSum = 0;
    for (int i = 0; i < N - 1; ++i) {
        int currentSum = prefixDistinct[i] + suffixDistinct[i + 1];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }

    cout << maxSum << endl;
    return 0;
}

Submission Info

Judge Result