Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray.

More formally, given an array \(a_1, a_2, \ldots, a_n\), you need to compute the value:

\[ \max_{1 \leq i \leq j \leq n} \left\{ \sum_{k=i}^{j} a_k \right\} \]

If the array is empty, then the result is defined as 0.

This problem can be solved efficiently using Kadane's algorithm, which uses the recurrence:

\[ \text{current} = \max(a_i, \text{current} + a_i) \]

and updates the global maximum accordingly.

inputFormat

The input is given from standard input (stdin). The first line contains a single integer \(n\) which represents the number of elements in the array. If \(n = 0\), the array is empty. The second line (if \(n > 0\)) contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum of any contiguous subarray of the given array.

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

6