I am trying to solve a sorting problem in which it would be useful to determine the longest increasing subsequence in a double ended queue.

As an example, let’s take the following sequence:

5, 3, 4, 2, 1

In the textbook problem we would consider this object to be an array and so the LIS here would simply be 3, 4.

However, if we consider this object to be a double ended queue, meaning the first element and the last element (or front and back) are connected, then the LIS could be 1, 3, 4 or also 2, 3, 4 due to the circular nature of the deque.

To be more clear, the sequence 5, 3, 4, 2, 1 is just one permutation of 1, 5, 3, 4, 2 where the front element has been popped to the back.

Now my question is, is there a clever way to find the LIS for this kind of circular object?

I had the idea to apply a LIS algorithm to every single array permutation for the queue but that would scale quadratically which would be terrible for performance.

I have a feeling there is a very simple answer to this question and maybe it is my lack of familiarity with LIS algorithms that is hindering me from seeing a more efficient solution..