Maximum Subarray Sum

Given an array A of n integers, find the contiguous subarray (containing at least one number) which has the largest sum and output this sum. In other words, you are to compute the value $$\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k.$$

Your solution must run in O(n) time; a well-known approach is Kadane's algorithm.

inputFormat

The first line contains an integer n, representing the number of elements in the array. The second line contains n space-separated integers describing the array.

outputFormat

Print a single integer representing the maximum contiguous subarray sum.## sample

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

6