Largest Contiguous Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. This problem is a classic example that can be efficiently solved using Kadane's Algorithm.

For an array \(arr\), the maximum contiguous subarray sum is defined as:

\(\text{max extunderscore sum} = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} arr[k]\)

If the array is empty, the result is defined to be 0.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array. If \(n = 0\), the second line may be empty.

outputFormat

Print a single integer representing the maximum sum of any contiguous subarray. The output should be written to standard output (stdout).

5
1 2 3 4 5

15