Finding the max of each continguous subarray of a given size
<p>I'm trying to solve the following problem in Python</p>

<blockquote>
  <p>Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.</p>
</blockquote>

<p>The idea is to use a double ended queue. This is my code:</p>

<pre><code>def diff_sliding_window(arr, win):
#     max = -inf
    Q = []
    win_maxes = [] # max of each window
    for i in range(win):
        print(Q)
        while len(Q) &gt; 0 and arr[i] &gt;= arr[len(Q) - 1]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('&gt;&gt;', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) &gt; 0 and Q[0] &lt;= i - win:
            Q.pop()
        while len(Q) &gt; 0 and arr[i] &gt;= arr[len(Q)-1]:
            Q.pop(0)
        Q.append(i)
#     win_maxes.append(arr[Q[0]])

    print(arr[Q[0]])
</code></pre>

<p>But I can't figure out why for the test cases:</p>

<pre><code>t1 = [1, 3, -1, -3, 5, 3, 6, 7]
t2 = [12, 1, 78, 90, 57, 89, 56]
</code></pre>

<p>that I'm not getting the correct results.</p>

<hr>

<p><strong>Update</strong>:</p>

<p>I've made the changes that Matt Timmermans suggested, but I'm still not obtaining the proper output. For <code>t2</code>, and <code>win = 3</code></p>

<pre><code>78
90
90
89 &lt;--- should be 90
89
</code></pre>

<p>Here is my updated code:</p>

<pre><code>from collections import deque

def diff_sliding_window(arr, win):
#     max = -inf
    Q = deque()
    win_maxes = [] # max of each window
    for i in range(win):
#         print(Q)
        while len(Q) &gt; 0 and arr[i] &gt;= arr[Q[len(Q)-1]]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('&gt;&gt;', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) &gt; 0 and Q[0] &lt;= i - win:
            Q.pop()
        while len(Q) &gt; 0 and arr[i] &gt;= arr[Q[len(Q)-1]]:
            Q.popleft()
        Q.append(i)


    print(arr[Q[0]])
</code></pre>

<p>What about this approach (which only needs one pass over the data):</p>

<h3>Code</h3>

<pre><code>def calc(xs, k):
    k_max = []
    result = []

    for ind, val in enumerate(xs):
        # update local maxes (all are active)
        for i in range(len(k_max)):
            if val &gt; k_max[i] :
                k_max[i] = val
        # one new sub-array starts
        k_max.append(val)

        if ind &gt;= (k-1):  # one sub-array ends
            result.append(k_max[0])
            k_max.pop(0)

    return result

t1 = [1, 3, -1, -3, 5, 3, 6, 7]
t2 = [12, 1, 78, 90, 57, 89, 56]
print(calc(t1, 3))
print(calc(t2, 2))
</code></pre>

<h3>Output</h3>

<pre><code>[3, 3, 5, 5, 6, 7]
[12, 78, 90, 90, 89, 89]
</code></pre>

python algorithm data-structures queue