Maximum Subarray Sum

Given a sequence of integers representing, for example, the number of vehicles passing through a checkpoint over a series of hours, your task is to find the contiguous subarray (containing at least one number) that has the maximum sum and output that sum.

This problem is a classic example solved using Kadane's algorithm. The formula used in Kadane's algorithm is:

\( current = \max(a_i, current + a_i) \)

and the answer is \( \max_{i}(current) \). Note that the subarray must consist of consecutive elements.

inputFormat

The input is given via stdin in the following format:

• The first line contains an integer \( n \) indicating the number of elements in the array.
• The second line contains \( n \) space-separated integers.

outputFormat

Print the maximum sum of any contiguous subarray to stdout in a single line.

## sample

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

6

</p>