Find max difference for a given array

Question

You are given an array of N integers, find the Max Difference where the index of largest number is greater than the index of the smallest number. If not find the next smallest number, so on and so forth. If this condition cannot be met, return -1

Sample Input                        Sample Output

values = [1, 2, 3, 4, 5]                  4

values = [2, 3, 4, 5, 1]                  3

values = [121, 30, 45, 55, 1]             -1

My solution, Python 2.7

def findNewIndex(max_index, min_index, input_array):
    input_array.pop(min_index)

    num = min(input_array)
    min_index = input_array.index(num)

    if max_index > min_index:
        return input_array[max_index] - input_array[min_index]
    elif max_index < min_index and input_array:
        return  findNewIndex(max_index, min_index, input_array)
    else:
        return -1

def maxDifference(input_array):
    max_num = max(input_array)
    max_index = input_array.index(max_num)

    min_num = min(input_array)
    min_index = input_array.index(min_num)

    if max_index > min_index:
        print input_array[max_index] - input_array[min_index]
    else:
       ans =  findNewIndex(max_index, min_index, input_array)
       print ans

I'd like feedback on the solution, is this a good way to solve it? Any improvements I can make to the code in terms of performance/style?

Answer 1

Overcomplicating

To start with, if what we're looking for is just the smallest number to the left of the largest number, we can make that algorithm more explicit:

def max_difference(xs):
    max_idx, max_elem = max(enumerate(xs), key=operator.itemgetter(1))

    if max_idx == 0:
        return -1
    return max_elem - min(xs[:max_idx])

Rather than making 4 passes to find the max and min elements and their respective indices, we can find the max element and its index in a single pass (taking advantage of enumerate and the fact that max takes a key function), and then simply searching the left side of that for the min element.

We don't need a findNewIndex-type method since once we know where the max element is and its index, that defines the domain for where the min element could be. We don't have to pop elements to find it.

A single pass

We can do better though. For each element, we can keep track of the smallest element we've seen so far and the largest element we've seen so far, and simply update as appropriate: the min element can get smaller, the max diff can only get bigger we see the new biggest:

def max_difference(xs):
    min_elem = xs[0]
    max_elem = xs[0]
    max_diff = -1

    for elem in xs[1:]:
        min_elem = min(elem, min_elem)
        if elem > max_elem:
            max_diff = max(max_diff, elem - min_elem)
            max_elem = elem

    return max_diff

Naming

The python style guide prefers snake_case to camelCase.

Answer 2

You need docstrings and better names. People had to get clarification from the comments to understand what was happening here, and your code doesn't make it any clearer. maxDifference doesn't just find the maximum difference from a list, and findNewIndex will actually return the difference result, never an index. This makes it very hard to follow what's going on in your code. A docstring explaining the algorithm goes a long way:

def max_sequential_difference(input_array):
    """Returns the difference of the largest int and its smallest preceding value."""

That's as brief and clear as I could make it. Now that this is what the problem statement is, it becomes easier to grasp what should happen and frankly this makes for a much easier solution to the problem. Now you could just get the max value, find its index and then get the minimum of the elements in the list preceding it.

def max_sequential_difference(input_array):
    """Returns the difference of the largest int and its smallest preceding value."""
    max_value = max(input_array)
    max_index = input_array.index(max_value)

    # If it's the first element
    if max_index == 0:
        return -1

    # Get the minimum value that exists before max_value
    min_value = min(input_array[:max_index])
    return max_value - min_value