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 and j. 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.