Page not loading? Try clicking here.
Placeholder

#1836
Subtask

Sum of Contiguous Subarray 1s 32MB

Problems

Given an array of N integers, write a program to find the maximum sum of a contiguous subarray.

A contiguous subarray means a sequence of consecutive numbers in the array.
Note: Choosing no elements at all is allowed, in which case the sum is 0.


Input

The first line contains an integer N (1 ≤ N ≤ 10^5).

The second line contains N integers, representing the array elements in order.

  • Each number is in the range [-100, 100].


Output

Print the maximum contiguous subarray sum for the given input.


Subtask

# Score Condition
#111

All numbers are non-negative (0 ≤ number ≤ 100)

#238

1≤N≤10^3

#351

1≤N≤10^5


Example #1

4

1 2 -2 4
5

Example #2

10

3 -4 0 1 7 -4 13 -9 8 -3
17


Source

JUNGOL

You must sign in to write code.