Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. In other words, identify the subarray (containing at least one element) which has the largest sum, and return that sum.

Formally, for an array \(a_1, a_2, \dots, a_n\), you need to find the maximum value of \(\sum_{i=l}^{r} a_i\) for any \(1 \le l \le r \le n\). This problem is typically solved using Kadane's algorithm.

Input is given via standard input and output should be written to standard output.

inputFormat

The input consists of two lines:

• The first line 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 representing the maximum sum of any contiguous subarray.

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

6