18_Google_Max_of_Subarray.py

'''
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.
You can modify the input array in-place and you do not need to store the results.
You can simply print them out as you compute them.
'''


def max_subarray(arr, k):
    result = []

    for i in range(len(arr)):
        slice = arr[i: i+k]

        if len(slice) == k:
            result.append(max(slice))
        else:
            # reached a point in the string where there are no more k contiguous subsets
            break

    return result

if __name__ == '__main__':
    test = [10, 5, 2, 7, 8, 7]
    print(max_subarray(test, k=3))