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 :A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10.A = {3,1,8}, k = 2, Max for 1st block = 3, 2nd block = 8, So sum is 11.A = {2,5,2}, k = 1, Max for 1st block = 2, 2nd block = 5, third block = 2. So sum is 9.A = {2,5,2}, k = 3, Max for only block = 5. So sum is 5.
Sum of Maximum of continuous blocks of length k
arrays;maximum subarray
For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:Initialize $D$ with $A_1,\ldots,A_k$, and initialize the sum $S$ with $\max D$.For $i=k+1,\ldots,n$:Remove $A_{i-k}$ from $D$.Add $A_i$ to $D$.Add $\max D$ to $S$.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.