Search for a subarray with maximum sum (Kadane's algorithm)

Java Medium arrays

Task «Search for a subarray with maximum sum (Kadane's algorithm)»

Given an array of integers, find the subarray (continuous sequence of elements) with the maximum sum. Output this sum. If the array consists only of negative numbers, output the maximum negative number (i.e., the smallest in absolute value).

Input Format

The first line contains an integer N (1 ≤ N ≤ 10^5) — the number of elements. The second line contains N integers separated by spaces — the elements of the array.

Output Format

Output a single integer — the maximum subarray sum.

Examples

Example 1

INPUT

3
abc
abcd
ab

OUTPUT

abcd

Example 2

INPUT

4
-1 -2 -3 -4

OUTPUT

-1

Example 3

INPUT

5
1 3 2 4 1

OUTPUT

11

Example 4

INPUT

2
a
bb

OUTPUT

NO

main.java