The sum of the maximum element of the sliding window of length K

Question

I recently ran into a problem. For part of the algorithm, it is required to calculate the sum of the maximum element of the sliding windows of length K. Where K is in the range from 1 <= K <= N (length N of the array).

Example if I have an array A as 5,3,12,4
Sliding window length 1: 5 + 3 + 12 + 4 = 24
Sliding window 2: 5 + 12 + 12 = 29 long
Sliding window 3: 12 + 12 = 24 long
4: 12 sliding window

Final answer is 24,29,24,12 .

I tried using this O (N ^ 2) . For each sliding window of length K, I can calculate the maximum in O (N). Since K is up to N. Therefore, the total complexity turns out to be O (N ^ 2) .
I am looking for O (N) or O (NlogN) or something similar to this algorithm, for example N, possibly up to 10 ^ 5.
Note: Elements in the array can be like 10 ^ 9 , so print the final answer modulo 10 ^ 9 + 7

EDIT: what do I really want to find for each value of K (i.e., from 0 to N) in total linear time or in O (NlogN) not in O (KN) or O (KNlogN), where K = {1,2 , 3, .... N}

Answer 1

Here is a brief outline of O (n).

For each element, determine how many adjacent elements on the left are no more (call it a ), and how many adjacent elements on the right are less (call it b ). This can be done for all O (n) time elements - see MBo answer.

A single element is maximum in its window if the window contains an element and only elements from a on the left and b on the right. Taking the opportunity, the number of such windows of length k (and, therefore, the total contribution of these windows) is piecewise linear in k, with no more than five parts. For example, if a = 5 and b = 3 , then there are

 1 window of size 1 2 windows of size 2 3 windows of size 3 4 windows of size 4 4 windows of size 5 4 windows of size 6 3 windows of size 7 2 windows of size 8 1 window of size 9. 

The data structure that we need to efficiently code this contribution is the Fenwick tree, whose values ​​are not numbers, but linear functions of k. For each linear part of the piecewise linear contribution function, we add it to the cell at the beginning of its interval and subtract it from the cell at the end (closed beginning, open end). At the end, we get all the prefix sums and evaluate them by index k to get the final array.

(OK, we need to complete it for now, but we don’t really need the Fenwick tree for the second step, which reduces complexity to O (n), and there may be a way to take the first step in linear time.)

Python 3 lightly tested:

 def left_extents(lst): result = [] stack = [-1] for i in range(len(lst)): while stack[-1] >= 0 and lst[i] >= lst[stack[-1]]: del stack[-1] result.append(stack[-1] + 1) stack.append(i) return result def right_extents(lst): result = [] stack = [len(lst)] for i in range(len(lst) - 1, -1, -1): while stack[-1] < len(lst) and lst[i] > lst[stack[-1]]: del stack[-1] result.append(stack[-1]) stack.append(i) result.reverse() return result def sliding_window_totals(lst): delta_constant = [0] * (len(lst) + 2) delta_linear = [0] * (len(lst) + 2) for l, i, r in zip(left_extents(lst), range(len(lst)), right_extents(lst)): a = i - l b = r - (i + 1) if a > b: a, b = b, a delta_linear[1] += lst[i] delta_linear[a + 1] -= lst[i] delta_constant[a + 1] += lst[i] * (a + 1) delta_constant[b + 2] += lst[i] * (b + 1) delta_linear[b + 2] -= lst[i] delta_linear[a + b + 2] += lst[i] delta_constant[a + b + 2] -= lst[i] * (a + 1) delta_constant[a + b + 2] -= lst[i] * (b + 1) result = [] constant = 0 linear = 0 for j in range(1, len(lst) + 1): constant += delta_constant[j] linear += delta_linear[j] result.append(constant + linear * j) return result print(sliding_window_totals([5, 3, 12, 4])) 

Answer 2

We define for each element the interval where this element dominates (maximum). We can do this in linear time by using forward and reverse runs using the stack. Arrays L and R will contain indices from the interval of domination.

To get left and right indexes:

 Stack.Push(0) //(1st element index) for i = 1 to Len - 1 do while Stack.Peek < X[i] do j = Stack.Pop R[j] = i //j-th position is dominated by i-th one from the right Stack.Push(i) while not Stack.Empty R[Stack.Pop] = Len //the rest of elements are not dominated from the right //now right to left Stack.Push(Len - 1) //(last element index) for i = Len - 2 to 0 do while Stack.Peek < X[i] do j = Stack.Pop L[j] = i //j-th position is dominated by i-th one from the left Stack.Push(i) while not Stack.Empty L[Stack.Pop] = -1 //the rest of elements are not dominated from the left 

The result for the array is (5,7,3,9,4).
For example, 7 dominates in the interval 0..2, 9 at 0..4

 i 0 1 2 3 4 X 5 7 3 9 4 R 1 3 3 5 5 L -1 -1 1 -1 4 

Now for each element we can consider its effect in all possible amounts.
Element 5 dominates in the interval (0,0); it is summed only in k = 1 record sum
Element 7 dominates in the interval (0.2), it is summed once in k = 1 sum, twice in k = 2, once in k = 3.
Element 3 dominates in the interval (2.2); it is summed only in k = 1 sum of entries
Element 9 dominates in the interval (0.4); it is summed once in k = 1 sum, twice in k = 2, twice in k = 3, twice in k = 4, once in k = 5.
Element 4 dominates in the interval (4.4); it is summed only in k = 1 sum.

In general, an element with a long interval of dominance in the center of a long array can give up to k * The value of the impact in the sum of k-length (this depends on the position relative to the ends of the array and other dom elements.)

 k 1 2 3 4 5 -------------------------- 5 7 2*7 7 3 9 2*9 2*9 2*9 9 4 -------------------------- S(k) 28 32 25 18 9 

Note that the sum of the coefficients is N * (N-1) / 2 (equal to the number of possible windows), most of the entries in the table are empty, so the complexity seems to be better than O (N ^ 2)
(I still doubt the exact difficulty)

Answer 3

The sum of the maximum in sliding windows for a given window size can be calculated in linear mode using a double queue that stores elements from the current window. We save deque so that the first (index 0, left most) element in the queue is always the maximum for the current window.

This is done by iterating through the array and at each iteration, first we delete the first element in deque if it is no longer in the current window (we do this by checking its original position, which is also stored in deque along with its value). Then we remove any elements from the end of the deque that are smaller than the current element, and finally, we add the current element to the end of the deque.

The complexity is O (N) to calculate the maximum for all sliding windows of size K. If you want to do this for all K values ​​from 1..N, then the complexity of the time will be O (N ^ 2), O (N) is the best time to calculate the sum of the maximum values ​​of all windows of size K (this is easy to see). To calculate the sum for other values ​​of K, a simple approach is to repeat the calculation for each different value of K, which will lead to a total time of O (N ^ 2). Is there a better way? No, because even if we save the calculation result for one value of K, we cannot use it to calculate the result for another value of K in less time O (N). Therefore, the best time is O (N ^ 2).

The following is the implementation in python:

 from collections import deque def slide_win(l, k): dq=deque() for i in range(len(l)): if len(dq)>0 and dq[0][1]<=ik: dq.popleft() while len(dq)>0 and l[i]>=dq[-1][0]: dq.pop() dq.append((l[i],i)) if i>=k-1: yield dq[0][0] def main(): l=[5,3,12,4] print("l="+str(l)) for k in range(1, len(l)+1): s=0 for x in slide_win(l,k): s+=x print("k="+str(k)+" Sum="+str(s))