# Most Efficient Solution explained in detail

#1

// Time Complexity: O(NlogN)
// Space Complexity: O(N);

int Solution::solve(vector &A) {
int n = A.size(), num, sum, maxSum = INT_MIN;
vector rightMax(n), leftMax(n);
rightMax[n - 1] = A[n - 1];
leftMax[0] = A[0];
set left;
left.insert(A[0]);

``````// Construct right max array
for(int i = n - 2; i >= 0; --i) {
/*
If max till now is greater than current number,
update right max of current number to max till now
*/
if(rightMax[i + 1] > A[i]) {
rightMax[i] = rightMax[i + 1];

// Current number is greater than max till now
} else {
rightMax[i] = A[i];
}
}

// Maintain a sorted list of numbers till current index
for(int i = 1; i < n; ++i) {
// Insert current number
left.insert(A[i]);

auto it = left.find(A[i]);

/*
If current number is not the smallest number,
update its leftMax to the number just left to it
*/
if(it != left.begin()) {
--it;
leftMax[i] = *it;

/*
Number is smallest and hence no number smaller than
it exists on its left
*/
} else {
leftMax[i] = A[i];
}
}

for(int i = 0; i < n; ++i) {
/*
If leftMax of any number is equal to number
itself than this denotes we didn't find any number
on the left of that number which is greater than it.
Same for rightMax
*/
if(A[i] != rightMax[i] && A[i] != leftMax[i]) {
sum = A[i] + rightMax[i] + leftMax[i];
maxSum = max(maxSum, sum);
}
}
return maxSum;
``````

}