Tổng lớn nhất của mảng con có đầu và cuối bằng nhau trong C++

Cho mảng số nguyên. Tìm mảng con (liền kề) có tổng lớn nhất sao cho phần tử đầu và cuối của mảng con đó bằng nhau.

Thuật toán

• Tính mảng tiền tố pr.
• Dùng unordered_map lưu chỉ số đầu tiên (first) và cuối cùng (last) của mỗi giá trị.
• Với mỗi chỉ số i, xem mảng con từ first[a[i]] đến last[a[i]], tính tổng bằng mảng tiền tố.
• Lấy max.

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

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

int maxValue(int a[], int n) {
    unordered_map<int, int> first, last;
    int pr[n];
    pr[0] = a[0];
    for (int i = 1; i < n; i++) {
        pr[i] = pr[i-1] + a[i];
        if (first[a[i]] == 0) first[a[i]] = i;
        last[a[i]] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int start = first[a[i]];
        int end = last[a[i]];
        ans = max(ans, pr[end] - (start ? pr[start-1] : 0));
    }
    return ans;
}

int main() {
    int arr[] = {1, 3, 5, 2, 4, 18, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxValue(arr, n);
    return 0;
}

Đầu ra

37