DCP18 - Max of Subarrays

'''
This problem was asked by Google.
Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.
For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:
10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)
Do this in O(n) time and O(k) space.
'''

def maxOfSubarrays(arr, k):
    if k <= 0 or k > len(arr) or k != int(k):
        return "Error using function maxOfSubarrays"
    subArrays = list()
    for i in range(len(arr) + 1 - k):
        subArray = list()
        for j in range(k):
            subArray.append(arr[i+j])
        subArrays.append(subArray)
    # Now, the list subArrays contains all the subArrays of length k given the array "arr"
    maxes = list()
    for sub in subArrays:
        maxes.append(max(sub))
    return subArrays, maxes

def prettyPrint(arr, k):
    print("*****************************************************")
    print("Array = " + str(arr) + ", k = " + str(k))
    subArrays, maxes = maxOfSubarrays(arr, k)
    for i in range(len(subArrays)):
        print("SubArray = " + str(subArrays[i]) + " ----> Max = " + str(maxes[i]))
    print("Maxes = " + str(maxes))
    print("*****************************************************")
    print()

# MAIN FUNCTION
arr1 = [10, 5, 2, 7, 8, 7]
k1 = 3
arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k2 = 5
prettyPrint(arr1, k1)
prettyPrint(arr2, k2)