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.

  1. https://www.geeksforgeeks.org/difference-between-stdsetlower_bound-and-stdlower_bound-in-c/
  2. https://codeforces.com/blog/entry/20553

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