D. Maximum Xor Secondary

D. Maximum Xor Secondary

Link for the problem:- D. Maximum Xor Secondary

Solution:

As we can see, there is no need to check for every interval. Just care about the first maximum and second maximum interval. While a new element came into the view, pop the top element in the stack, and check the corresponding interval until the new element is greater than the top element in the stack. We can easily see it is correct since we won’t lose the answer as long as it exists.
Time complexity of this solution is O(n).

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],i,j,k,mx=0;
    stack<int> st;
    for(i=0;i<n;i++)
    cin>>a[i];
    for(i=0;i<n;i++)
    {
        while(!st.empty())
        {
            mx=max(mx,st.top()^a[i]);
            if(st.top()<a[i])
            st.pop();
            else
            break;
        }
        st.push(a[i]);
    }
    cout<<mx;
    return 0;

}