Profits

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.

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

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

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