public int[] maxSubArray(int input[], int k) {
        Deque<Integer> queue = new LinkedList<Integer>();
        int max[] = new int[input.length - k + 1];
        int maxVal = Integer.MIN_VALUE;
        //first find max of first k values and make it 0th element of max array
        for (int i = 0; i < k; i++) {
            if(maxVal < input[i]){
                maxVal = input[i];
            }
            if (queue.isEmpty()) {
                queue.offerLast(i);
            } else {
                while (!queue.isEmpty() && input[queue.peekLast()] <= input[i]) {
                    queue.pollLast();
                }
                queue.offerLast(i);
            }
            
        }
        max[0] = maxVal;
        int index=1;
        //continue from k till end of the input array
        for (int i = k; i < input.length; i++) {
            //if index of peek is k distance from i then its no value to us.
            //throw it away
            if (i - k + 1 > queue.peekFirst()) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && input[queue.peekLast()] <= input[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            //Only reason first element survived was because it was biggest element.
            //make it the max value for this k
            max[index] = input[queue.peekFirst()];
            index++;
        }
        return max;
    }
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
Test cases
input containg neg and pos values
val of k is neg 0 or pos
val of k is larger than size of input
val of k is same as size of input
src/com/interview/array/MaximumOfSubarrayOfSizeK.java