Maximum subarray sum

Problem

A shop records the profit or loss of each day. Find the largest total that any run of consecutive days gives. The run must contain at least one day.

Example

Input

6
3 -5 4 -1 3 -2

Output

The run 4, -1, 3 gives 6.

Try the problem first. Open one hint at a time.

Hint 1

At each day, either extend the run that ends yesterday or start a new run today.

Hint 2

Start both numbers from the first item so an all-negative list works.

Write your Python code, run it on the examples and submit it to hidden tests.