Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and output its sum. This problem is a classic and can be solved efficiently using Kadane's algorithm.

Formally, given an array ( a_1, a_2, \dots, a_n ), find ( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k ).

inputFormat

The first line contains a single integer ( n ) ( (1 \leq n \leq 10^5) ) denoting the number of elements in the array. The second line contains ( n ) space-separated integers ( a_1, a_2, \dots, a_n ) where each ( a_i ) satisfies ( -10^9 \leq a_i \leq 10^9 ).

outputFormat

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

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

6