828. 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, the size of the array. The second line contains n space-separated integers, the elements of the array.

Output Format

Print the sum of the maximum 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