Tổng lớn nhất cửa sổ trong mảng A sao cho cửa sổ cùng vị trí trong mảng B không trùng lặp C++

Cho hai mảng A, B cùng kích thước. Tìm cửa sổ con (liền kề) trong A có tổng lớn nhất sao cho các phần tử tương ứng trong B là duy nhất (không trùng).

Thuật toán (Cửa sổ trượt + Hash Set)

• Duyệt i từ 0 đến n-1, mở rộng cửa sổ phải.
• Dùng unordered_set theo dõi giá trị B trong cửa sổ.
• Nếu B[i] đã có trong set: thu hẹp cửa sổ trái (xóa A[left], B[left]) cho đến khi B[i] không còn trong set.
• Cập nhật tổng cửa sổ và max.

Ví dụ triển khai (C++)

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

int returnMaxSum(int A[], int B[], int n) {
    unordered_set<int> seen;
    int result = 0, curr_sum = 0, left = 0;
    for (int i = 0; i < n; ++i) {
        while (seen.count(A[i])) {
            seen.erase(A[left]);
            curr_sum -= B[left];
            left++;
        }
        seen.insert(A[i]);
        curr_sum += B[i];
        result = max(result, curr_sum);
    }
    return result;
}

int main() {
    int A[] = {0, 1, 2, 3, 0, 1, 4};
    int B[] = {9, 8, 1, 2, 3, 4, 5};
    int n = sizeof(A)/sizeof(A[0]);
    cout << returnMaxSum(A, B, n);
    return 0;
}

Đầu ra

20