favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

# Thylacine

Given the sequence of n integers. Find its nonempty subsequence of consecutive numbers, such that the sum of these numbers is maximal.

#### Input

First line contains number n (1n106). Second line contains the sequence elements, each of them is no more than 1000.

#### Output

Print the maximum sum of numbers in non-empty sub-sequence of consecutive numbers.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
6
4 2 3 -7 8 1

Output example #1
11

Input example #2
8
2 -1 4 3 -8 6 -3 4

Output example #2
8

Input example #3
3
-12 -6 -1

Output example #3
-1