Finding the largest of each subarray of length k

Question

Interview Question: - Given the array and integer k, find the maximum for each adjacent k-sized array.

Sample Input :

1 2 3 1 4 5 2 3 6 

3 [ value of k ]


Sample Output :
3
3
4
5
5
5
6

I can’t think of anything better than brute force. The worst case is O (nk), when the array is sorted in descending order.

Answer 1

Just iterate over the array and save the klast elements in a self-balancing binary tree .
Adding an item to such a tree, deleting the item and searching for current maximum costs O(logk).

. STL, IIRC, MultiSet. Java TreeMap (map, , , Java Multi- ).

for (int i = 0; i < n; ++i) {
    tree.add(a[i]);

    if (tree.size() > k) {
        tree.remove(a[i - k]);
    }

    if (tree.size() == k) {
        print(tree.max());
    }
}

Answer 2

O (n) O (n).

.

[a1 a2 ... ak] [a(k+1) ... a2k] ...

, .

i- . I- .

k.

, max a[i... i+k], , k.

[j-k+1 ... i i+1 ... j] [j+1 ... i+k ... j+k]

, , RightMax i to j j+1 to i+k .

Answer 3

Hope this is the solution you are looking for:

def MaxContigousSum(lst, n):
m = [0]
if lst[0] > 0:
    m[0] = lst[0]
maxsum = m[0]
for i in range(1, n):
    if m[i - 1] + lst[i] > 0:
        m.append(m[i - 1] + lst[i])
    else:
        m.append(0)
    if m[i] > maxsum:
        maxsum = m[i]
return maxsum

lst = [-2, 11, -4, 13, -5, 2, 1, -3, 4, -2, -1, -6, -9]
print MaxContigousSum(lst, len(lst))
**Output**
20 for [11, -4, 13]