Maximum Subarray Sum

In this problem, you are given an array of integers and you need to find the maximum sum of any contiguous subarray. This is a classic problem that can be effectively solved using Kadane's algorithm.

Recall that for an array (a_1, a_2, \ldots, a_n), the task is to find indices (i) and (j) such that (\sum_{k=i}^{j}a_k) is maximized.

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single integer which is the maximum subarray sum.## sample

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

6