Length of longest increasing subarray after rotating array left/right

Question

I encountered this problem on a competitive programming platform:

Given an array of length N and Q queries, where a query is either left or right rotation of the array. Find the length of longest sub-array in array after every rotation.

Although an O(N * Q) approach was an acceptable answer, I can't help but think there there must be a faster approach since every rotation would modify length of only 2 potential sub-sequences.

I thought about duplicating the array and appending the duplicate array to get an array of length 2N:

So then if I take a window of size N:

• with 0 rotations, answer would be longest increasing subarray in range [0, N - 1] where the window would start.
• with 1 left rotation, answer would be longest subarray in range [1, N], i.e. move the window right by 1 unit.
• with k left rotations, answer would be in range[k, N - 1 + k] which would be moving window right by k units from initial position.

I was planning to save the answers for all possible queries by shifting the window right by 1 unit until I have checked for N-1 left rotations.

Finding longest subarray for the range [0, N - 1] would be O(N) but I am not able to reduce time taken after every window shift.

I had thought of using a priority queue, where I would store every index in the window and the length of longest subarray possible with the said index as start, and use the length of the subarray as priority. I am having troubles with updating the queue after a shift. I had initially thought that I would not have to make too many updates bringing down the algorithm's complexity down to O(N logN) but here I am not updating the subarray that were added before the window is shifted.

I feel that if the priority queue is managed properly, the complexity could be brought down to O(N logN) from preprocessing and O(1) per query.

Edit: The question was actually about longest increasing subarray, but I had used subsequence instead of using the word subarray which has been corrected after the edit.

Answer 1

Consider duplicated sequence (like you suggested). Try to group up elements such that if ai <= ai+1 then ai should be in the same group as ai+1. In that way you will divide the sequence into increasing continuous subsequences. Store those subsequences as pairs (begin, end). You can get a sorted list of them in O(N).

Now let's calculate the results for all cyclic shifts. Let's start with the first N elements. Create a BST that will sort subsequences by their length. Insert all subsequences that end before N. If there is any subsequence that starts before N and ends after it (or later any subsequence that starts before our window and ends inside), we shall call it special. To get the result just take the maximum of length of subsequences in BST and a part of special ones that lies within the considered window. When you move to the next shift, the special one may fit entirely, so just insert it to the BST. You may also need to delete from BST an subsequence that starts before the window (it then becomes the special one). So you can get the maximum length from all the subsequences in the BST in O(log n) and from the special ones in O(1) (there are at most two of them at the same time).

You can even go for a O(n) complexity by changing BST into a queue (it is sometimes called min/max queue, or sliding window maximum/minimum, or whatever else, it enables to get minimum/maximum of elements, adding new one and deleting the first one added all in O(1))