Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and output that sum. This problem is a classic example of the Maximum Subarray problem, often solved using algorithms such as Kadane's algorithm or the divide and conquer approach. In mathematical terms, for an array \( a[0 \dots n-1] \), you need to compute

\[ \max_{0 \leq i \leq j < n} \sum_{k=i}^{j} a[k] \]

Note that the subarray should contain at least one element.

inputFormat

The first line of input contains a single integer \( n \) (\( 1 \leq n \leq 10^5 \)), representing the number of elements in the array. The second line contains \( n \) space-separated integers \( a[0], a[1], \dots, a[n-1] \) where each \( a[i] \) is in the range of \( -10^9 \) to \( 10^9 \).

outputFormat

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

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

6