Maximum Subarray Sum

You are given an array of n integers. Your task is to compute the maximum possible sum of any contiguous subarray.

Formally, given an array \(a_1, a_2, \ldots, a_n\), find the maximum value of \(\sum_{i=l}^{r} a_i\) over all \(1 \leq l \leq r \leq n\). This problem can be solved efficiently using Kadane's algorithm.

Input: The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), the number of elements in the array. The second line contains \(n\) space-separated integers, where each integer \(a_i\) satisfies \(|a_i| \leq 10^4\).

Output: Output a single integer representing the maximum subarray sum.

inputFormat

The input is given from standard input (stdin) in the following format:

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) integers separated by spaces.

outputFormat

Output a single integer to standard output (stdout), which is the maximum subarray sum.

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

6