435. Maximum Subarray

0

Medium

Given an array of integers, find the sum of the contiguous subarray with the largest sum and return the sum.

Input Format

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

Print 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^9
-10^4 <= nums[i] <= 10^4

Loading...

View Submissions

Console