Maximum Subarray Sum

Given an array of integers, your task is to find the largest sum of any contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's algorithm. In particular, for each index ( i ), update the current maximum subarray sum by the formula:

[ max_current = \max(a_i, max_current + a_i) ]

The overall maximum is the largest ( max_current ) encountered during the traversal of the array. Note that if the input array is empty, the output should be 0. Consider edge cases such as all negative numbers or a single element array.

inputFormat

The input begins with a single integer ( n ) which denotes the number of elements in the array. If ( n ) is greater than 0, the next line contains ( n ) space-separated integers representing the array elements. If ( n == 0 ), there are no further inputs.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray from the given list.## sample

4
3 -2 5 -1

6