Maximum Subarray Sum

You are given an array of integers. Your task is to compute the maximum sum of any contiguous subarray.

In other words, given an array \(a_1, a_2, \dots, a_n\), find the value of \[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \]

If the array is empty, consider the maximum sum as 0.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer n representing the number of elements in the array. If n = 0, the array is empty.

The second line (if n > 0) contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer via standard output (stdout): the maximum sum of any contiguous subarray.

0

0