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 return its sum. This problem is a classic application of Kadane's algorithm, which efficiently solves the problem in O(n) time.

The mathematical formulation of the problem is given by: \( \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k \), where \(a_k\) represents the k-th element of the array.

If the array is empty, output 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer n (0 ≤ n ≤ 10⁵), the number of elements in the array.
• If n > 0, the second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the maximum subarray sum to standard output (stdout).

5
1 2 3 4 5

15