# TLE for O(nlogn) solution using Sparse Table

#1

Algo:

1. Create sparse table.

2. for each element a in array, assume it is the middle element.

3. Query sparse table to find the max Value in left subarray which is less than a and max Value in the right subarray which is greater than a.

4. In each for such query, q(x,y) : get index of max value in subarray A[x…y]=t.

5. If A[t]<lowerLimit or A[t]>upperLimit, fire recursive queries q(x,t-1) & q(t+1,y) and get the result.
Space complexity: O(nlogn)
Time Complexity: O(nlong)

public class Solution {

public int solve(int[] A) {
int n=A.length,ans=0;
if(n<=2) return -1;
int sp[][]=buildSpTable(A);
for(int i=1;i<n-1;i++){
int lq=q(A,sp,0,i-1,Integer.MIN_VALUE,A[i]),rq=q(A,sp,i+1,n-1,A[i],Integer.MAX_VALUE),sum=-1;
if(lq>=0 && lq<n && rq>=0 && rq<n) sum=A[lq]+A[i]+A[rq];
ans=Math.max(ans,sum);
}
return ans;
}
int[][] buildSpTable(int A[]){
int n=A.length,sz=log2(n)+1;
int sp[][]=new int[sz][n];
for(int i=0;i<sz;i++){
for(int j=0;j<n;j++){
if(i==0){
sp[i][j]=j;
continue;
}
//sp[i][j]=min{sp[i-1][j],sp[i-1][j+2^(i-1)]}
sp[i][j]=sp[i-1][j];
int r=j+pow2(i-1);
//System.out.print(" r="+r);
if(r<n && A[sp[i-1][j]]<A[sp[i-1][r]])
sp[i][j]=sp[i-1][r];
}
}

return sp;
}
int q(int A[], int sp[][], int x, int y, int lowerLimit, int upperLimit){
//find the index of max value in A[x....y]<limit
int n=A.length;
if(x>y || x>=n || y>=n || x<0 || y<0) return -1;

if(x==y){
if(A[x]>lowerLimit && A[x]<upperLimit) return x;
return -1;
}
int k=log2(y-x);
//ans=max{sp[k][x],sp[k][y-pow2(k)+1]}
int ans=sp[k][x],r=y-pow2(k)+1;
if(r<n && sp[k][r]<n && sp[k][x]<n && A[sp[k][x]]<A[sp[k][r]])
ans=sp[k][r];
if(A[ans]>lowerLimit && A[ans]<upperLimit) return ans;

int lq=q(A,sp,x,ans-1,lowerLimit,upperLimit),rq=q(A,sp,ans+1,y,lowerLimit,upperLimit);
if(lq==-1 && rq==-1) ans=-1;
else if(lq==-1) ans=rq;
else if(rq==-1) ans=lq;
else ans = (A[lq]>=A[rq])?lq:rq;
return ans;
}
int pow2(int n){
return 1<<n;
}
int log2(int n){
return (int)(Math.log(n)/Math.log(2));
}

}