Finding largest from each subarray of length k

Interview Question :- Given an array and an integer k , find the maxim开发者_如何学JAVAum for each and every contiguous sub array of size k.

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 cant think of anything better than brute force. Worst case is O(nk) when array is sorted in decreasing order.

Just iterate over the array and keep k last elements in a self-balancing binary tree.
Adding element to such tree, removing element and finding current maximum costs O(logk).

Most languages provide standard implementations for such trees. In STL, IIRC, it's MultiSet. In Java you'd use TreeMap (map, because you need to keep count, how many times each element occurs, and Java doesn't provide Multi- collections).

Pseudocode

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());
    }
}

You can actually do this in O(n) time with O(n) space.

Split the array into blocks of each.

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

For each block, maintain two more blocks, the left block and the right block.

The ith element of the left block will be the max of the i elements from the left. The ith element of the right block will be the max of the i elements from the right.

You will have two such blocks for each block of k.

Now if you want to find the max in range a[i... i+k], say the elements span two of the above blocks of k.

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

All you need to do is find the max of RightMax of i to j of the first block and the left max of j+1 to i+k of the second block.

Hope this is the solution which 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]