Maximum Subarray Sum

You are given an array of integers. Your task is to find the sum of the largest contiguous subarray using Kadane's Algorithm.

The contiguous subarray should contain at least one number.

The problem requires you to implement an efficient solution with a linear time complexity.

Mathematical Formulation:

Let \(a_1, a_2, \ldots, a_n\) be an array of integers. Find indices \(i\) and \(j\) such that \[ S = \sum_{k=i}^{j} a_k \] is maximized, and output the maximum sum \(S\).

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

You can assume \(n \ge 1\).

outputFormat

Output a single integer which is the sum of the largest contiguous subarray.

## sample

5
1 2 3 4 5

15