Maximum Subarray Sum

This is a classical problem in dynamic programming. Given an array of integers \(a_1, a_2, \dots, a_n\), you are required to compute the maximum sum of any contiguous subarray. Formally, find the value of

$$\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k,$$

where the subarray can be empty (in which case the answer is defined to be 0). Your solution should correctly handle all cases including arrays with all positive numbers, all negative numbers, a mix of both, and the empty array.

inputFormat

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

• The first line contains a single integer n representing the number of elements in the array.
• If n > 0, the second line contains n space-separated integers representing the elements of the array. If n = 0, the second line is omitted.

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum of a contiguous subarray.

## sample

1
5

5

</p>