# Solved in O(NLog(N)) time and O(N) space

#1

int getLowValue(set& lowValue, int& n)
{
auto it = lowValue.lower_bound(n);
–it;
return (*it);
}
int Solution::solve(vector &A) {
set s;
s.insert(INT_MIN);
int n=A.size(),ma=0;
int m[n];
m[n-1]=A[n-1];
for(int i=n-2;i>=0;i–)
m[i]=max(A[i],m[i+1]);

``````for(int i=0;i<n-1;i++)
{
if(A[i]<m[i+1])
{
ma=max(ma,A[i]+m[i+1]+getLowValue(s,A[i]));

s.insert(A[i]);
}
}

return ma;
``````

}

#2

Its giving TLE!!
int sum = 0, n = A.size();
vector maxx(n+1);
for(int i=n-1; i>=0; i–){
maxx[i] = max(maxx[i+1],A[i]);
}
set s;
s.insert(INT_MIN);
s.insert(A[0]);
for(int i=1; i<n-1; i++){
int right = maxx[i+1];
if(right<=A[i]){
continue;
}
auto it = lower_bound(s.begin(),s.end(),A[i]);
it–;
int left = *it;
s.insert(A[i]);
sum = max(sum,left+right+A[i]);
}
return sum;

#3

isn’nt it giving TLE

#4

I don’t understand this. Both the solutions above use the same approach. Why does one give a TLE and other does not. (First one doesn’t give TLE while the second one does)

#5

I tried to run this code. If I am finding the lower bound (int left) in the loop itself, it is giving TLE but when i am writing a separate function to find lower bound from set s, it is getting accepted.

#6

It is giving TLE due to this line:
`auto it = lower_bound(s.begin(),s.end(),A[i]);`
By using -
`auto it=s.lower_bound(A[i]);`

this problem can be solved. I also faced the same problem, then got to know about it. You can refer to the below articles to get better insights.

Hope it helps!

#7

why this code is not working?
def solve(self, A):
n=len(A)
summ=max_sum=0
for i in range(n):
pivot=A[i]
while pivot>A[i+1] and i < n-2:
i=i+1

``````        if i == n-2 :
continue
else:
pivot2=A[i+1]

while pivot2>A[i+1] and i < n-1 :
i=i+1

if i==n-1:
continue
else:
pivot3=A[i+1]
summ=pivot1+pivot2+pivot3

if summ>max_sum:
max_sum=summ

if max_sum==0:
return 0

return max_sum``````