Maximum Sum Triplet

 https://www.interviewbit.com/old/problems/maximum-sum-triplet/

 

maximum suffix array:

2 5 3 6 1 4  1  ->        6  6  6  6  4  4  1

     for(int i=n-1;i>=0;i--)
    {
        right[i]=el;
        el=max(A[i],el);
    }

 

int Solution::solve(vector<int> &A) {
    int n=A.size(),el=A[n-1],ans=0;
    // Right[i] indicates the max element after A[i]
    vector<int>right(n); //maximum suffix array
    set<int>s;
    s.insert(A[0]);
    for(int i=n-1;i>=0;i--)
    {
        right[i]=el;
        el=max(A[i],el);
    }
    for(int i=1;i<n-1;i++)
    {
        //If there is no element greater than A[i] to the right then A[i] can't be a middle element
        if(right[i]<=A[i])
        {
            continue;
        }
        s.insert(A[i]);
        auto it=s.find(A[i]); // after inserting  in set the elements get sorted.
        // If there is no element lesser than A[i] to it's left then A[i] can't be a middle element
        if(it==s.begin()) // if after finding A[i] it points to begin means no element is smaller than it
        {
            continue;
        }
        // else get the maximum element,leser than A[i], to the left of A[i]
        it--;
        ans=max(ans,*it+A[i]+right[i]);
    }
    return ans;
}