Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any non-empty contiguous subarray. This is a classic problem that can be solved efficiently using Kadane's Algorithm. The key recurrence in the algorithm is given by the latex formula: $$max_{current} = \max(a_i, max_{current}+a_i)$$, which helps to decide whether to start a new subarray at the current element or extend the previous subarray.

You are guaranteed that the array contains at least one element.

inputFormat

The first line of input contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers which are the elements of the array.

outputFormat

Output a single integer, which is the maximum sum of any contiguous subarray found in the array.

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

6