Maximum average. Write a program that finds a contiguous subarray of length at most m in an array of n long integers that has the highest average value among all such subarrays, by trying all...

Maximum average. Write a program that finds a contiguous subarray of length at most m in an array of n long integers that has the highest average value among all such subarrays, by trying all subarrays. Use the scientific method to confirm that the order of growth of the running time of your program is mn². Next, write a program that solves the problem by first computing the quantity prefix[i] = a[0] + ... + a[i] for each i, then computing the average in the interval from a[i] to a[j] with the expression (prefix[j] - prefix[i]) / (j - i + 1). Use the scientific method to confirm that this method reduces the order of growth by a factor of n.