Though i understood what is being done in th problem but I cant figure out the logic people have been using to solve this problem using stack.
Example solution : Submission #33238326 - Codeforces
So I need help with this logic.
Secondly when i tried the test case:
4
6 5 4 1
The code gives output as 5. But the actual answer must be 7 i.e. 6^1.
So did they forgot to add this test case or I am wrong somewhere…?
Your test case is wrong, yes, since subarray 1…4 will use 6 ^ 5 instead of 6 ^ 1. Remember, its the max and second max.
For the logic, you can understand it like this:
Fix a[i] as the maximum element.
We can see when we pick a left bound j and there exist index k as the maximum element of the segment a[j] -> a[i], it’s no different from picking k as the left bound. Therefore, only pick left bounds j if a[j] is the maximum of the segment a[j] -> a[i].
Let’s pretend we already have a list of possible left bounds right now. It’s clear that if it’s (j1, j2, …, jk), we will have a[jk] < … < a[j2] < a[j1].
Try j[k] as a left bound, then j[k - 1], j[k - 2], …, j[2] and j[1]. However, we can see that when we get to a certain j[pos] > a[i], every pick from pos - 1 and below will have j[pos] as the second maximum and itself as the maximum, therefore we discard after we get to that point.
Now our problem is how to get a list of possible left bounds efficiently. We can simulate this by a stack. While we can still pick a j[k] < a[i], keep popping it off the stack. Then finally, push a[i] into the stack. The required property is still maintained correctly.
Complexity is O(N), since every element is pushed into the stack and popped just once.