Maximum Subarray Sum

Given an array of integers, find the maximum sum of any non-empty sublist (subarray) that consists of consecutive elements. Using Kadane's algorithm, you can solve this problem in O(n) time by iterating through the array and keeping track of the current sublist sum.

The problem can be formally defined as finding
\( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \) ,

where \(a_1, a_2, \dots, a_n\) are the elements of the array.

Your program should read the array from standard input and output the maximum subarray sum to standard output.

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_1, a_2, \dots, a_n\), which can be positive, negative, or zero.

outputFormat

Output a single integer which is the maximum sum of any non-empty contiguous subarray.

5
1 2 -3 4 5

9