This seems to work; can it be made more efficient?


#1

int Solution::solve(vector &A) {
int n = A.size();
int sumMax = 0;
int Ai, Aj, Ak;

// Sorted set of possible Ai values
set<int> s;
s.insert(INT_MIN);

// Array of maximum Ak values
int m[n];
m[n-1] = A[n-1];
for (int k = n - 2; k >= 0; k--)
    m[k] = max(A[k], m[k+1]);
    
// Try each possible Aj
for(int j = 0; j < n-1; j++) {
    Aj = A[j];
    Ak = m[j+1];
    if (Aj < Ak) {
        auto it = s.lower_bound(Aj);
        it--;
        Ai = *it;
        sumMax = max(sumMax, Ai + Aj + Ak);
        s.insert(Aj);
    }
}
return sumMax;

}