Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray that has the largest sum and output that sum. In other words, you need to compute $$\max_{1\le i\le j\le n}\sum_{k=i}^{j}a_k,$$ where \(a_k\) are the elements of the array. Note that if all numbers are negative, the answer is the maximum (i.e., the least negative) among them.

This problem can be solved efficiently using Kadane's Algorithm.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of elements in the array.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^9\)), which are the elements of the array.

outputFormat

Output a single integer: the sum of the contiguous subarray with the largest sum.

## sample

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

6

</p>