Best run of days

Problem

A shop records profit or loss for each day. Choose a run of consecutive days, at least one day long, with the largest total. Print that total.

Example 1

Input

3 -5 4 -1 3 -2

Output

Days 3 to 5 give 4 - 1 + 3 = 6.

Example 2

Input

-4 -2 -7

Output

-2

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

Hint 1

Let cur be the best run that ends today. Either start fresh today or extend yesterday's run.

Hint 2

The answer is the largest cur seen, not the last one.

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