Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output that sum. This problem can be efficiently solved using Kadane's algorithm. Mathematically, you are to compute:

$$\max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k$$

The array may contain both positive and negative integers. Ensure that your solution correctly handles cases where all elements are negative.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n, representing the number of elements in the array. The second line contains n space-separated integers, which are the elements of the array.

outputFormat

Output a single integer to standard output (stdout) representing the maximum sum of any contiguous subarray.## sample

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

6