Maximum Subarray Sum

Given an array of integers, find the sum of the contiguous subarray (containing at least one number) which has the largest sum.

This problem can be solved efficiently using Kadane's Algorithm. The algorithm works by iterating through the array while maintaining the current maximum subarray sum max_current and a global maximum max_global. The recurrence relation used is:

\( max_{current} = \max(a_i, max_{current} + a_i) \)

and then update \( max_{global} \) if \( max_{current} \) is greater.

Note that if the array is empty, the output should be 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 representing the elements of the array.

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