Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any non-empty contiguous subarray. A contiguous subarray is a sequence of adjacent elements within the array. The challenge is to identify the subarray whose elements sum to the highest possible value.

The well-known Kadane's Algorithm can solve this problem in linear time. Its key recurrence is given by:

$$ max\_current = \max(a_i,\; max\_current + a_i) $$

where a_i is the current element of the array. Implement this algorithm to compute the desired maximum subarray sum.

inputFormat

The first line of input contains an integer n, 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 — the maximum sum of a contiguous subarray.

## sample

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

6

</p>