Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum. Formally, for an array (a_1, a_2, \dots, a_n), you need to compute (\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k). This problem can be efficiently solved using Kadane's algorithm.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

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

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

6