1. You are given an array(arr) of integers. 2. You have to find maximum subarray sum in the given array. 3. The subarray must have at least one element.
Input Format
A number N a1 a2.. N integers
Output Format
A number representing maximum subarray sum in the given array.
Constraints
1 <= N <= 10000 -2^31 <= arr[i] <= 2^31 - 1
Example
Input
3 1 2 3
Output
6