ORIGINAL CODING QUESTION
Sum of rolling window peaks
Take the maximum of each length-k contiguous window and return the sum of these maxima.
Original exercise · medium. Editorial role relevance does not imply a company has asked this question.
Input and output
n, then n signed values, then k.
Constraints
1 ≤ n ≤ 200; -100 ≤ value ≤ 100; 1 ≤ k ≤ n.
Example 1
Input
5 1 3 2 5 4 3
Output
13
Window maxima are 3,5,5, totaling 13.
Example 2
Input
3 -3 -2 -1 2
Output
-3
Window maxima total -3.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Discard indexes that are outside the window.
Hint 2
A decreasing deque keeps the current maximum at its front.
Hint 3
Remove weaker candidates from the back before inserting a new value.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →