Problem Statement 
 We want to find the location of a local maximum in an unknown function. y = f(x) is
a continuous realvalued function defined on the real numbers.
We already have a number of data pairs, (xi, yi), and we need to find
a small interval on the x axis that is guaranteed to contain at least one local (or global)
maximum.
But taking a sample from this function
is quite expensive so we are only allowed to take N samples. Our problem is to
choose them in such a way as to minimize the size of the interval that we
determine.
The sampling will be done sequentially: we choose a value of x and find the
corresponding y value, f(x). We repeat this process N times, choosing the x value based on
all the data collected so far.
We are willing
to assume that no two y values will be exactly equal to each other.
Create a class LocalMax that contains a method length that is given N, the
number of samples we can take, and double[]s xData and yData
(the existing data pairs). It will return the worst case length for our interval
around a local maximum using optimal sampling. If it is not possible to make such
a guarantee, it returns 1.0.


Definition 
 Class:  LocalMax  Method:  length  Parameters:  int, double[], double[]  Returns:  double  Method signature:  double length(int N, double[] xData, double[] yData)  (be sure your method is public) 




Notes 
  The returned value must be accurate to within a relative or absolute value of 1E9 

Constraints 
  N will be between 0 and 25 inclusive. 
  xData will contain between 1 and 50 elements inclulsive. 
  yData will contain the same number of elements as xData. 
  The elements of yData will be distinct. 
  The elements of xData will be distinct. 
  Each element of xData and yData will be greater than 0.0 and less than 10000.0. 

Examples 
0)  
  Returns: 1.0 
From the data we already have we cannot guarantee that this function even
has a local maximum  it might be monotonically increasing.



1)  
  Returns: 2.0 
We know that there is a local maximum between x=3 and x=5. 


2)  
  Returns: 2.0 
Here is one way (there are others) get an interval of length 2 or less
with just two additional samples. Take the
first sample at x=6.5. The worst case is that the corresponding
y value is less than 923.2. In that case we know that the interval
(3,6.5) contains a local maximum, and that the y value at x=5 is greater than
either endpoint y value. Take the second sample at x=4.7. In the worst case
the corresponding value of y will be bigger than 923.2, in which case we
could conclude that there is a local max somewhere in the interval (3,5).



3)  
  Returns: 1.0 
If we take a sample at x=4.0+epsilon, for some tiny epsilon, then the
worst case would be that the corresponding y value would be smaller than
53. In that case the interval between 3.0 and 4.0+epsilon would contain
a local maximum. So by choosing epsilon arbitrarily small, we get an
interval whose length is (arbitrarily close to) 1.0.



4)  
 3  {1,4.3,7.2,95.4,534.0}  {72, 83, 19, 25.3, 624.0} 
 Returns: 1.4500000000000002  
