Maximum Subarray Sum

You are given an array of integers and your task is to find the maximum sum of any contiguous subarray. A subarray is a contiguous part of an array and can range from a single element to the entire array.

The solution should be efficient with a time complexity of \(O(n)\). This problem can be solved using Kadane's algorithm, which iterates through the array while maintaining the maximum subarray sum ending at the current index.

Note: The contiguous subarray must contain at least one number.

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.

outputFormat

Output a single integer which is the maximum subarray sum.

## sample

4
3 -2 5 -1

6

</p>