So you have an array that is ordered from highest to lowest, and now you need to know what is the maximum difference between consecutive elements in the array.  So let’s take a look at what we are first talking about.

int[] array = {1,2,3,5,7,11,13,17,19}

As you can see we have an ordered list.  We can easily see that the maximum difference between the elements is 4.  11-7 and 17-13 both result in 4.  Now what if this array was  a size in thousands.  What would be the best way to calculate this value?

I have found a divide and conquer approach that works extremely well to reduce the over all number of checks needed.

/*******************************************************************************
 * Copyright (c) 2017 MyMiller Consulting LLC.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 *******************************************************************************/
package name.mymiller.algorithms;
 
import java.util.ArrayList;
import java.util.List;
 
import name.mymiller.exceptions.OutOfOrderException;
 
/**
 * Class of static methods for various algorithm implementations
 *
 * @author jmiller
 *
 */
public class Algorithms
{
    /**
     * Process an sorted array to identify the MAX difference between elements
     *
     * @param array
     *            Array to analyze
     * @return Maximum difference between two consecutive elements in the array.
     * @throws OutOfOrderException
     *             Exception throw to indicate Array is out of order
     */
    static public int maxDiff(int[] array) throws OutOfOrderException
    {
 
        return Algorithms.maxDiff(array, 0, array.length - 1, 0);
    }
 
    /**
     * Process an sorted array to identify the MAX difference between elements
     *
     * @param array
     *            Array to analyze
     * @param start
     *            Position to start analyzing
     * @param end
     *            Position to stop analyzing
     * @return Maximum difference between two consecutive elements in the array.
     * @throws OutOfOrderException
     *             Exception throw to indicate Array is out of order
     */
    static public int maxDiff(int[] array, int start, int end) throws OutOfOrderException
    {
        return Algorithms.maxDiff(array, start, end, 0);
    }
 
    /**
     * Process an sorted array to identify the MAX difference between elements
     *
     * @param array
     *            Array to analyze
     * @param start
     *            Position to start analyzing
     * @param end
     *            Position to stop analyzing
     * @param currentMax
     *            Maximum difference known
     * @return Maximum difference between two consecutive elements in the array.
     * @throws OutOfOrderException
     *             Exception throw to indicate Array is out of order
     */
    static private int maxDiff(int[] array, int start, int end, int currentMax) throws OutOfOrderException
    {
        final int range = Math.abs(array[end] - array[start]);
        if (array[start] > array[end])
        {
            throw new OutOfOrderException("Array is not ordered. Index:(" + start + ") " + array[start]
                    + " is greater than Index:(" + end + ") " + array[end]);
        }
        if (start >= end)
        {
            return 0;
        }
        else if (range <= currentMax)
        {
            return 0;
        }
        else if (((start + 1) == end) || (range <= 1))
        {
            return range;
        }
        else
        {
            final int mid = ((end - start) / 2) + start;
 
            final int maxFront = Algorithms.maxDiff(array, start, mid, currentMax);
            final int maxBack = Algorithms.maxDiff(array, mid, end, (maxFront > currentMax) ? maxFront : currentMax);
 
            return (maxFront > maxBack) ? maxFront : maxBack;
        }
    }
}

This works through a divide and conquer algorithm.  We split the array, and check each section separately.  The key is we pass in what is known as the current maximum.  Then we check to determine if the entire array from start to finish is less than the current known maximum, if it is then we continue checking it, otherwise we don’t need to follow on that array any further.  This leads to more checks early while we are finding the maximum, with fewer checks occurring once we get closer to the maximum.