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;

}