Maximum Subarray Sum

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

For example, if the input array is [1, 2, -3, 4, 5], the maximum subarray sum is 9, which comes from the subarray [4, 5].

The solution should be efficient enough to handle large input sizes, ideally in O(n) time complexity using Kadane's algorithm.

If the array is empty (i.e. the size is zero), the output should be 0.

inputFormat

The first line contains an integer n (n ≥ 0) 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 subarray sum.

5
1 2 -3 4 5

9