Nice solution (both O(nlogn) and O(n^2)) to this interesting question


#1

This is O(nlogn) solution, for O(n^2) solution, you can uncomment the commented part and comment the section of code as indicated.

int Solution::solve(vector &A) {
vector grtr(A.size());
int max = INT_MIN;
for (int i=A.size()-1; i>=0; i–){
if (max > A[i])
grtr[i] = max;
else {
grtr[i] = 0;
max = A[i];
}
}
// comment from here
int ret = INT_MIN;
set st;
st.insert(A[0]);
for (int i=1; i<A.size()-1; i++){
auto itr = st.lower_bound(A[i]);
itr = itr == st.begin() ? st.end() : --itr;
if (itr != st.end() && grtr[i]){
if (*itr + A[i] + grtr[i] > ret){
ret = *itr + A[i] + grtr[i];
}
}
st.insert(A[i]);
}
return ret == INT_MIN ? 0 : ret;
// till here
// max = INT_MIN;
// int ret = INT_MIN;
// for (int i=1; i<A.size()-1; i++){
// for (int j=0; j<i; j++){
// if (A[j] < A[i] && max < A[j])
// max = A[j];
// }
// if (max != INT_MIN && grtr[i]){
// if (max + A[i] + grtr[i] > ret){
// ret = max + A[i] + grtr[i];
// }
// }
// max = INT_MIN;
// }
// return ret == INT_MIN ? 0 : ret;
}