Maximum Subarray Sum

You are given an array of integers. Your task is to find a contiguous subarray (containing at least one number) which has the largest sum and output its sum.

Mathematically, if the array is denoted by \(a_1, a_2, \dots, a_n\), you need to compute:

\[ \text{max\_sum} = \max_{1 \le i \le j \le n} \left(\sum_{k=i}^{j} a_k\right)\]

This is a classical application of Kadane's algorithm. Try to implement it in an efficient manner.

inputFormat

The first line contains a single integer \(N\) denoting the number of elements in the array. The second line contains \(N\) space-separated integers representing the array elements.

outputFormat

Output a single integer, the sum of the contiguous subarray with the maximum sum.

## sample

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

6