Giá trị xóa lớn nhất (Maximum Erasure Value) trong C++

Cho mảng số nguyên dương. Xóa một mảng con (subarray) liên tiếp chứa các phần tử **duy nhất** (không trùng lặp). Giá trị thu được = tổng các phần tử mảng con đó. Tìm giá trị lớn nhất có thể.

Đầu vào 1: {1,2,4,5,6} → Đầu ra: 17 (mảng con {2,4,5,6}).

Đầu vào 2: {5,3,1,3,5,3,1,3,5} → Đầu ra: 9 (mảng con {5,3,1} hoặc {1,3,5}).

Phương pháp: Cửa sổ trượt (Sliding Window)

Duy trì cửa sổ [i, j] chứa các phần tử duy nhất. Dùng unordered_set theo dõi phần tử trong cửa sổ. Mở rộng j, nếu arr[j] đã có trong set → thu hẹp cửa sổ từ trái (i) cho đến khi xóa phần tử trùng. Cập nhật tổng cửa sổ và kết quả max.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

int maximumUniqueSubarray(vector<int> &arr) {
    unordered_set<int> seen;
    int res = 0, sum = 0, i = 0;
    for (int j = 0; j < arr.size(); j++) {
        while (seen.count(arr[j])) {
            seen.erase(arr[i]);
            sum -= arr[i];
            i++;
        }
        seen.insert(arr[j]);
        sum += arr[j];
        res = max(res, sum);
    }
    return res;
}

int main() {
    vector<int> nums = {5,3,1,3,5,3,1,3,5};
    cout << maximumUniqueSubarray(nums);
    return 0;
}

Kết quả

9

Phức tạp O(n) thời gian, O(n) không gian.