How can I efficiently find the largest positive interval in an unsorted array?
Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.