Prefix Maxima — Solution & Editorial

Back to the Problem

Sweep once carrying the maximum so far.

Complexity: O(N)