Maximum Subarray Sum

Given an integer array of (n) elements, find the contiguous subarray (containing at least one number) which has the largest sum and output its sum. Formally, for an array (a_1, a_2, \dots, a_n), you need to compute (\max_{1 \le i \le j \le n} \left(\sum_{k=i}^{j} a_k\right)). In the case of an empty array, the answer is defined to be 0.

inputFormat

The input is read from standard input (stdin). 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 which represent the elements of the array. If (n = 0), no further input is provided.

outputFormat

Output a single integer to standard output (stdout) which is the sum of the contiguous subarray with the largest sum.## sample

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

6