Cheap and Secure Web Hosting Provider : See Now

# Sum of Maximum of continuous blocks of length k

, ,
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.

#### 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\$.
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.