Maximum Subarray Sum

Given an array of integers, your task is to find the maximum possible sum of a contiguous subarray. The subarray must contain at least one element.

This is a classic problem that can be solved optimally using Kadane's algorithm. The algorithm works in linear time by iterating through the array and keeping track of the maximum subarray sum ending at the current index.

Formally, for an array \(a_1, a_2, \dots, a_n\), you need to compute:

\( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \)

If the array is empty, output 0.

inputFormat

The input is provided from the standard input (stdin) and consists of two lines:

1. The first line contains an integer \(n\) \( (0 \leq n \leq 10^5)\), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers.

Note that if \(n = 0\), the second line will be empty.

outputFormat

Output a single integer to the standard output (stdout) representing the maximum sum of a contiguous subarray in the given array.

## sample

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

6