Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j]

max_distance.py

# http://leetcode.com/2011/05/a-distance-maximizing-problem.html

def max_distance(array):
    
    # collect possible starting points
    # alternative: only record index without the num
    starts = [(array[0], 0)]
    for i, each in enumerate(array):
        if each < starts[-1][0]:
            starts.append((each, i))
    
    # scan through the array from the end to find
    # possible ending points
    max_dis = 0; cursor = len(starts) - 1
    for i in range(len(array) - 1, 0, -1):
        while cursor >= 0 and array[i] > starts[cursor][0]:
            max_dis = max(max_dis, i - starts[cursor][1])
            cursor -= 1
        if cursor < 0: break
    
    return max_dis

max_distance([4, 3, 5, 2, 1, 3, 2, 3])  # 4
max_distance([1, 2, 3, 4, 5, 6])  # 5
max_distance([6, 5, 4, 3, 2, 1])  # 0
max_distance([6, 5, 4, 3, 4, 5])  # 3