Find the maximal difference between items u, v (where index(u) < index(v)) of a given sequence ``a``. Think stockmarket prices. Dynamic programming.

maximize.py

#!/usr/bin/env python

def maximize(a):    
    """ Find the maximal difference between items u, v
    (where index(u) < index(v)) of a given sequence ``a``. 
    Think stockmarket prices.
    
    Returns the actual difference, start and end position in ``a`` and
    the sublist yielding the best result.

    ``total`` holds the running total of the numbers
    ``mintotal`` is the minimal running total encoutered so far
    ``gap`` is the maximum difference

    >>> maximize([1, 1, 1, 1])
    (0, (0, 0), [1])

    >>> maximize([1, 1, 4, 1, 8])
    (7, (0, 4), [1, 1, 4, 1, 8])

    >>> maximize([1, 2, 3, 8, 1, 9])
    (8, (0, 5), [1, 2, 3, 8, 1, 9])
    
    >>> maximize([5, 3, 10, 18, 3, 27, 29, 1, 3, 9])
    (26, (1, 6), [3, 10, 18, 3, 27, 29])
    
    """
    total, mintotal, gap = 0, 0, 0
    last, first, candidate = 0, 0, 0

    for i in range(len(a) - 1):
        total += a[i + 1] - a[i]
        if total < mintotal:
            mintotal = total
            candidate = i + 1 # this is a new candidate for a starting index
        if total - mintotal > gap:
            first = candidate # the gap got bigger, we accept the candidate
            last =  i + 1
            gap = total - mintotal

    return gap, (first, last), (a[first:last + 1])

if __name__ == '__main__':
    import doctest
    doctest.testmod()