Solution: Scanning Every Window

The most direct idea is to look at each window on its own. For every starting position, scan the next k values and record the largest one. This is the brute force solution.

With our running example, values = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the windows are:

start 0: [ 1,  3, -1]              max 3
start 1: [ 3, -1, -3]              max 3
start 2: [-1, -3,  5]              max 5
start 3: [-3,  5,  3]              max 5
start 4: [ 5,  3,  6]              max 6
start 5: [ 3,  6,  7]              max 7

There are values.length - k + 1 windows, so the result array has that length.

Here is the implementation in Java:

public static int[] slidingMaximum(int[] values, int k) {
  int[] answer = new int[values.length - k + 1];
  for (int start = 0; start <= values.length - k; start++) {
    int max = values[start];
    for (int i = start + 1; i < start + k; i++) {
      if (values[i] > max) {
        max = values[i];
      }
    }
    answer[start] = max;
  }
  return answer;
}

This is a good solution in the sense that it is easy to understand and it is correct. The special cases are handled correctly as well. If k is 1, the inner loop runs zero times and each value is copied into the answer. If k is the whole array length, the outer loop runs once and computes the maximum of the whole array.

What does this cost? The outer loop runs once per window, and there are $n-k+1$ windows, which is at most $n$. For each window, the inner loop looks at k values. So the running time is $O(nk)$. The problem asks for $O(n)$.

You can see the repeated work if you look at two neighboring windows:

[1, 3, -1], -3
 1, [3, -1, -3]

These two windows share most of their values. The current solution discards everything after each window and starts over. We should perhaps carry something forward instead of starting over for each window.