Maximum Subarray Sum

Given an integer array, find the contiguous subarray (of at least one element) with the largest sum and output that sum.

This problem can be solved using Kadane's algorithm. More formally, given an array (a_1, a_2, \dots, a_n), compute (\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k). In case the array is empty, output 0.

inputFormat

The first line contains an integer (n) which represents the number of elements in the array. The second line contains (n) space-separated integers. If (n = 0), the array is considered empty.

outputFormat

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

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

6