## Finding Nearby Differences

# Finding Nearby Differences

Consider a one-based array *a* of integers of arbitrary
size. We will define the *distance-weighted difference*
*d(i,j)* between a distinct pair of numbers *a[i]* and
*a[j]* in the array to be the magnitude of the difference
between the numbers divided by the distance between their
positions:

d(i,j) = |a[i] - a[j]| / |i - j|

In this exercise, you are asked to give an algorithm for
finding an *i* and *j* that maximize *d(i,j)* for a given
array *a*.

Write a formal problem description. It should have a name, an instance description, and a solution specification.

Give an algorithm for solving instances of the problem. It need not be efficient.

Give the

*big-O*complexity of your algorithm. Be sure to specify what this complexity is a function of, and what your fundamental operation is.Give an argument for the correctness of your algorithm. It need not be a full formal proof, but should be sufficient to convince our graders that the algorithm is correct.

You may submit the assignment by typing or pasting it directly in to Moodle, or you may upload a PDF. It is fine to do your homework with paper and pencil and submit a PDF of a scan. You may *not* submit office file formats or the like: they're too hard for the graders to read.