Maximum Subarray Sum

Given an array of n integers, find the maximum sum of any non-empty contiguous subarray. A subarray is defined as a contiguous segment of the array. In mathematical notation, if the array is denoted by (A[1..n]), you are to compute

[ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} A[k] ]

This problem is commonly solved using Kadane's algorithm.

inputFormat

The first line contains a single integer (n) which denotes the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

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

1
1

1