I am trying to solve a sorting problem in which it would be useful to determine the longest increasing subsequence in a circular buffer.
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 circular buffer, 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.
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 pushed 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 buffer 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..
Assuming it's about a circular buffer (i_1,..,i_n), you can reduce the problem to finding the LIS in the array (i_1,..,i_n,i_1,..,i_n-1).
The time complexity for this would be O(n' log n') with n'=2n-1.
Edit:†
To avoid sequences that span more than the initial buffer:
While building up the candidates you just remember the starting index of the first element, and avoid adding elements which are farther away than n-1. This check can be added to the LIS algorithm without affecting its time complexity.
† Thank you @KonstantinMakarov for pointing out the flaw in the first draft.