Поиск максимальной суммы в подмассиве

Рассмотрим элемент a_i и некоторый отрезок [j..i] (то есть отрезок, для которого элемент a_i является последним). По условию нас интересуют только отрезки, у которых a_j == a_i. Поймём, какой из таких отрезков даёт наибольшую сумму. Распишем сумму отрезка (нумерация элементов в массиве с единицы):

sum([j..i]) = sum([1..i]) - sum([1..(j-1)])

Таким образом, для фиксированного i достаточно найти такой j, что sum([1..(j-1)]) минимальна. Это можно сделать с помощью хеш-таблицы, в которой для каждого числа a_i будем хранить минимальную из сумм sum([1..(j-1)]) для всех подходящих j.

typedef long long ll;
// для удобства добавим в начало массива ноль
vector<int> a = {0 /* extra zero */, 3, 5, 6, 3, 5};
// элементы массива индексируются [1..n]
int n = a.size() - 1;
// префиксные суммы
// cumsum[k] := a[1] + ... + a[k]
vector<ll> prefixSums;
for (int ai : a)
    prefixSums.push_back(prefixSums.empty() ? 0 : prefixSums.back() + ai);
// сумма на отрезке a_j ... a_i равна сумме на префиксе [1..i] минус сумме на префиксе [1..j-1]
// по условию задачи рассматриваются только такие суммы, что a_j == a_i
// будем итерироваться по массиву и для каждого числа a_j запоминать минимальную сумму на префиксе [1..j-1]
// при встрече очередного числа a_i будем обновлять ответ, рассматривая отрезок [j..i]
unordered_map<int, ll> numberToMinSum;
ll answer = numeric_limits<ll>::min();
for (int i = 1; i <= n; ++i) {
    if (numberToMinSum.find(a[i]) != numberToMinSum.end()) {
        numberToMinSum[a[i]] = min(numberToMinSum[a[i]], prefixSums[i - 1]);
        answer = max(answer, prefixSums[i] - numberToMinSum[a[i]]);
    } else {
        numberToMinSum[a[i]] = prefixSums[i - 1];
    }
}
cout << answer << endl;

Проверка на Ideone.