For example, given an array

a = [1, 2, 3, 7, 8, 9]

and an integer i = 2. Find maximal subarrays where the distance between the largest and the smallest elements is at most i. The output for the example above would be:

[1,2,3] [7,8,9]

The subarrays are maximal in the sense given two subarrays A and B. There exists no element b in B such that A b satisfies the condition given. Does there exist a non-polynomial time algorithm for said problem ?

CodePudding user response：

This problem might be solved in linear time using method of two pointers and two deques storing indices, the first deque keeps minimum, another keeps maximum in sliding window.

Deque for minimum (similar for maximum):

current_minimum = a[minq.front]

Adding i-th element of array: //at the right index

while (!minq.empty and a[minq.back] > a[i]): 
   //last element has no chance to become a minimum because newer one is better
   minq.pop_back
minq.push_back(i)

Extracting j-th element: //at the left index

if (!minq.empty and minq.front == j)
    minq.pop_front

So min-deque always contains non-decreasing sequence.

Now set left and right indices in 0, insert index 0 into deques, and start to move right. At every step add index in order into deques, and check than left..right interval range is good. When range becomes too wide (min-max distance is exceeded), stop moving right index, check length of the last good interval, compare with the best length.

Now move left index, removing elements from deques. When max-min becomes good, stop left and start with right again. Repeat until array end.