Profits

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of N daily profits, find the maximum sum over any contiguous stretch of days.

Level: Easy3 of 10
Topics: Array, Dynamic programming, Greedy, Prefix sum
Solved: No attempts yet

Problem

The cows have opened a new business, and Farmer John wants to see how well it is doing. The business has run for $N$ days ( $1 \le N \le 100{,}000$ ), and on each day $i$ the cows recorded their net profit $P_i$ ( $-1{,}000 \le P_i \le 1{,}000$ ).

Farmer John wants to find the largest total profit earned during any single consecutive stretch of days. Such a stretch may be as short as one day or as long as all $N$ days. Write a program that computes this largest possible sum of consecutive daily profits.

Input

Line 1: a single integer $N$ .
Lines $2$ through $N+1$ : line $i+1$ contains a single integer $P_i$ .

Output

Line 1: a single integer, the maximum sum of profits over any consecutive stretch of days.

Hint

In the sample, the maximum is obtained by summing the profits from day 2 through day 6 ( $4 + 9 - 2 - 5 + 8 = 14$ ).

Examples5

Example 1
Input
```
7
-3
4
9
-2
-5
8
-3
```
Expected output
```
14
```
Example 2
Input
```
1
5
```
Expected output
```
5
```
Example 3
Input
```
1
-7
```
Expected output
```
-7
```
Example 4
Input
```
5
-5
-2
-8
-1
-9
```
Expected output
```
-1
```
Example 5
Input
```
4
1
2
3
4
```
Expected output
```
10
```