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.
  • 1
    $\begingroup$ What are your thoughts on the question? We expect you to try to solve the question yourself and to explain where you got stuck. $\endgroup$ – Yuval Filmus Feb 14 '16 at 23:08
  • $\begingroup$ @EvilJS This gives an $O(nk)$ algorithm, whereas $O(n\log k)$ is possible. $\endgroup$ – 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:

  • Adding an element.
  • Removing an element.
  • Calculating the maximum.

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

  • $\begingroup$ 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. $\endgroup$ – Saurabh Jain Feb 14 '16 at 23:26
  • $\begingroup$ Yes, that's exactly your task. I won't give any further hints. The rest you can do yourself. $\endgroup$ – Yuval Filmus Feb 14 '16 at 23:36
  • $\begingroup$ I know Segment tree, but for all k = 1 to n, it will take (n^2)*logn time. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.