Largest Contiguous Subarray Sum

You are given an array of integers. Your task is to find the sum of the contiguous subarray within the array which has the largest sum.

This problem can be solved efficiently using Kadane's Algorithm. The algorithm works by iterating over the elements of the array and keeping track of two quantities: the maximum sum ending at the current position and the overall maximum sum found so far.

Formally, given an array \( A = [a_1, a_2, \dots, a_n] \), you are to compute the maximum value of \( \sum_{i=k}^{l} a_i \) for some \( 1 \le k \le l \le n \).

Constraints: The array may include positive, negative, and zero values.

inputFormat

The input is given on standard input (stdin) and consists of two lines. The first line contains a single integer \( n \) which denotes the number of elements in the array. The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output the sum of the contiguous subarray with the largest sum to standard output (stdout).

## sample

5
1 2 3 4 5

15

</p>