Maximum Contiguous Subarray Sum

Given an array of integers, your task is to find the contiguous subarray with the largest sum and output that sum. This problem can be solved using Kadane's algorithm. More formally, for an array \(a_1, a_2, \ldots, a_n\), find the maximum value of \(\sum_{i = l}^{r} a_i\) for any \(1 \le l \le r \le n\).

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output via standard output (stdout) a single integer which is the maximum sum of any contiguous subarray.

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

6