809. Maximum Contiguous Sum of Subarray

0

Medium

Given an array of size N and an integer N, find the maximum sum of a contiguous subarray (with at least one element) and return it. A subarray is a contiguous part of an array.

Input Format

The input consists of two lines. The first line contains an integer N, representing the size of the array. The second line contains N space-separated integers, representing the elements of the array.

Output Format

Output a single integer, representing the maximum sum of a contiguous subarray.

Example

Input

9
-2 1 -3 4 -1 2 1 -5 4

Output

6

Constraints

1 <= N <= 10^5

-10^4 <= arr[i] <= 10^4

-10^4 <= arr[i] <= 10^4

Loading...

View Submissions

Console