compute suffix maximums using itertools.accumulate

Question

What's the recommended way to compute the suffix maximums of a sequence of integers?

Following is the brute-force approach (O(n**2)time), based on the problem definition:

>>> A
[9, 9, 4, 3, 6]
>>> [max(A[i:]) for i in range(len(A))]
[9, 9, 6, 6, 6]

One O(n) approach using itertools.accumulate() is the following, which uses two list constructors:

>>> A
[9, 9, 4, 3, 6]
>>> list(reversed(list(itertools.accumulate(reversed(A), max))))
[9, 9, 6, 6, 6]

Is there a more pythonic way to do this?

Answer 1

Slice-reversal makes things more concise and less nested:

list(itertools.accumulate(A[::-1], max))[::-1]

It's still something you'd want to bundle up into a function, though:

from itertools import accumulate

def suffix_maximums(l):
    return list(accumulate(l[::-1], max))[::-1]

If you're using NumPy, you'd want numpy.maximum.accumulate:

import numpy

def numpy_suffix_maximums(array):
    return numpy.maximum.accumulate(array[::-1])[::-1]