Maximum Subarray Sum

Given an integer array, your task is to find the maximum sum of any contiguous subarray. That is, you need to determine the maximum value of the sum of a consecutive segment of the array. Formally, given an array \(A\) of size \(n\), you are to compute

$$\max_{0 \le i \le j < n} \sum_{k=i}^{j} A[k]$$

If the array is empty, the output should be \(0\).

inputFormat

The first line of input contains an integer (n) (where (n \ge 0)), 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 will be empty.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray.## sample

1
5

5