Challenge 1: Deviation
Given an array of integer elements and an integer d please
consider all the sequences of d consecutive elements in the
array. For each sequence we compute the difference between the maximum and the
minimum value of the elements in that sequence and name it the deviation.
Your task is to
·
write a function that
computes the maximum value among the deviations of all the sequences considered
above
·
print the value the
standard output (stdout)
Note that your function will receive the following arguments:
·
v
o which is the array of integers
·
d
o which is an integer value giving the length of
the sequences
Data constraints
·
the array will contain
up to 100,000 elements
·
all the elements in
the array are integer numbers in the following range: [1, 2^{31} 1]
·
the value of d will
not exceed the length of the given array
Efficiency constraints
·
your function is
expected to print the result in less than 2 seconds
Example
Input

Output

v: 6, 9, 4, 7, 4, 1
d: 3 
6

Explanation
The sequences of length 3 are:
·
6 9 4 having the
median 5 (the minimum value in the sequence is 4 and the maximum is 9)
·
9 4 7 having the
median 5 (the minimum value in the sequence is 4 and the maximum is 9)
·
7 4 1 having the
median 6 (the minimum value in the sequence is 1 and the maximum is 7)
·
The maximum value
among all medians is 6
package com.my.hired; import java.util.Random; public class MyClass { public static void main(String[] args) { Integer[] xx = new Integer[100000]; Random generator = new Random(); for (int i = 0; i < xx.length; i++) { xx[i] = generator.nextInt(100); } find_deviation(xx, 3); } public static void find_deviation(Integer[] v, Integer d) { long start = System.currentTimeMillis(); int finalArrayCount = 0; for (int count = 0; count < v.length; count++) { int min = 2147483647; int max = 1; for (int j = count; j < count + d; j++) { if (count + d > v.length) { break; } if (v[j] > max) { max = v[j]; } if (v[j] < min) { min = v[j]; } } if (finalArrayCount < (max  min)) { finalArrayCount = max  min; } } System.out.println(finalArrayCount); System.out.println((System.currentTimeMillis()  start) / 1000); } }