# Sum of Maximum of continuous blocks of length k

Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k?

Examples :

1. A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10.
2. A = {3,1,8}, k = 2, Max for 1st block = 3, 2nd block = 8, So sum is 11.
3. A = {2,5,2}, k = 1, Max for 1st block = 2, 2nd block = 5, third block = 2. So sum is 9.
4. A = {2,5,2}, k = 3, Max for only block = 5. So sum is 5.
• What are your thoughts on the question? We expect you to try to solve the question yourself and to explain where you got stuck. – Yuval Filmus Feb 14 '16 at 23:08
• @EvilJS This gives an $O(nk)$ algorithm, whereas $O(n\log k)$ is possible. – Yuval Filmus Feb 14 '16 at 23:36

For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:

1. Initialize $D$ with $A_1,\ldots,A_k$, and initialize the sum $S$ with $\max D$.

2. For $i=k+1,\ldots,n$:

1. Remove $A_{i-k}$ from $D$.
2. Add $A_i$ to $D$.
3. Add $\max D$ to $S$.
3. Return $S$.

The data structure has to support three kinds of operations:

• Removing an element.
• Calculating the maximum.

I'll let you figure out what data structure is most suitable, and what is the resulting complexity.

• If you could devise a data structure that will help in calculating Sum for all values from k = 1 to n, in O (n log n), then it will be pretty good solution and practical. – Saurabh Jain Feb 14 '16 at 23:26
• Yes, that's exactly your task. I won't give any further hints. The rest you can do yourself. – Yuval Filmus Feb 14 '16 at 23:36
• I know Segment tree, but for all k = 1 to n, it will take (n^2)*logn time. – Saurabh Jain Feb 14 '16 at 23:40

If you want all sums separately, just add up the first $k$ elements, for the next stretch add the $k + 1$-st and subtract the first, and keep going adding the next and subtracting the first one.

• You misunderstood the question. He wants $\sum_{i=1}^{N-k+1} \max(A_i,\ldots,A_{i+k-1})$. – Yuval Filmus Feb 14 '16 at 23:04