Maximum Subarray Sum

Given an array of n integers, find the maximum possible sum of any contiguous subarray.

The problem is a classical application of Kadane's Algorithm. You are required to implement an efficient solution that works for both positive and negative integers.

The maximum subarray sum is defined as the maximum sum of contiguous elements in the array. In mathematical terms, if the array is \( A = [a_1, a_2, \dots, a_n] \), then you need to compute:

\( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \)

The input is provided through stdin and the result should be printed to stdout.

inputFormat

The first line of the input contains an integer n denoting the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the maximum subarray sum.

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

6