Skip to content

Instantly share code, notes, and snippets.

@miku
Last active September 16, 2016 08:06
Show Gist options
  • Save miku/744438 to your computer and use it in GitHub Desktop.
Save miku/744438 to your computer and use it in GitHub Desktop.
Find the maximal difference between items u, v (where index(u) < index(v)) of a given sequence ``a``. Think stockmarket prices. Dynamic programming.
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment