Maximum Contiguous Subarray Sum

Given an array of integers, your task is to find the maximum possible sum of any contiguous subarray. In other words, if \(A = [a_1, a_2, \dots, a_n]\) then you need to compute \[ \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} a_k\right) \] for the best possible indices \(i\) and \(j\). This is a classic problem often solved using Kadane's algorithm.

The input begins with an integer \(n\), the number of array elements, followed by \(n\) space-separated integers. The output should be a single integer representing the maximum contiguous subarray sum.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), indicating the number of elements in the array. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray of the given array.

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

9