Find max difference for a given array
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 &gt; 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.