Maximum Subarray Sum

Given an array of integers, the goal is to find the maximum sum of a contiguous subarray. This problem is a classic challenge that can be efficiently solved using Kadane's Algorithm. The algorithm iterates over the array, and for each element \( a_i \), updates a running sum as:

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

and the maximum so far as:

\( max\_sum = \max(max\_sum, current\_sum) \).

Please implement the solution to read the input from standard input and output the answer to standard output.

inputFormat

The first line contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers, which are the elements of the array.

outputFormat

Output a single integer that is the maximum sum of any contiguous subarray.

8
-2 1 -3 4 -1 2 1 -5 4

6