Maximum Subarray Sum

Given an array of integers, find the maximum sum that can be obtained by summing up a contiguous subarray. This problem can be solved efficiently using Kadane's algorithm.

The objective is to find the maximum sum of any subarray, where a subarray is a contiguous part of the original array. In mathematical terms, if the array elements are \(a_1, a_2, \dots, a_n\), you should compute \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\).

Note that if all the numbers are negative, the answer is the largest (or least negative) number.

inputFormat

The first line contains a single integer \(n\), the number of elements in the array.

The second line contains \(n\) space-separated integers, which represent 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>