Asked in my Oracle OA last week.

A single pass with a running value is enough here. Keep track of the best answer so far and update it as you scan, which gives O(n) time and O(1) extra space.