Maximum Subarray Sum

This problem requires you to find the maximum possible sum of a contiguous subarray within a given array of integers. This is a classic problem that can be solved efficiently using Kadane's algorithm, which scans through the array and at each position, computes the maximum subarray ending at that position.

More formally, given an array \(A = [a_1, a_2, \dots, a_n]\), you need to determine the maximum value of \(\sum_{i=k}^{j} a_i\) for some \(1 \leq k \leq j \leq n\). In the case of an empty array, the answer is defined as 0.

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 denoting the elements of the array. If \(n = 0\), the second line will be empty.

outputFormat

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

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

6