Solved in O(2*n) ~ O(n)


#1

public int solve(ArrayList A) {
int ans=0;
int n=A.size();
int[] rmax=new int[A.size()];

    int max=A.get(n-1);
    
    for(int i=n-2;i>=0;i--){
        rmax[i]=max;
        max=Math.max(max,A.get(i));
    }
    
    
    Stack<Integer> st=new Stack<>();
    
    for(int i=0;i<n;i++){
        if(st.size()>0){
            
            while(st.size()>0 && st.peek()>rmax[i]){
                st.pop();
            }
            
            while(st.size()>0 && st.peek()<A.get(i) &&  A.get(i)<rmax[i]){
                ans=Math.max(ans,st.peek()+A.get(i)+rmax[i]);
                st.pop();
            }
        }
        st.push(A.get(i));
    }
           return ans;
}

#2

I don’t think this is correct. Can you please explain what’s your approach?