Maximum Subarray Sum

You are given an array of integers which may be empty. Your task is to compute the maximum sum of any contiguous subarray within this array. If the array is empty, the answer is 0.

This is a classic problem, often solved using Kadane's Algorithm. The algorithm iterates over the list, maintaining the maximum subarray sum ending at each position, and updates the overall maximum accordingly.

Mathematically, if we denote the array as \(a_1, a_2, \dots, a_n\), we want to compute \[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \] with the convention that for an empty array the sum is 0.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(n\) which denotes the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), then the array is empty.

Example:

5
1 2 3 4 5

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray. The result should be printed via standard output (stdout).

Example:

15

## sample

0

0

</p>