Cheap and Secure Web Hosting Provider : See Now

Sum of Maximum of continuous blocks of length k

, , No Comments
Problem Detail: 

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.
Asked By : Saurabh Jain

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53101

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback