Maximum Subarray Sum

You are given an array of integers. Your task is to find the sum of the contiguous subarray which has the maximum sum. In other words, find a subarray that gives the maximum possible sum and output that sum. If the array is empty, output 0.

This problem can be solved efficiently using Kadane's algorithm, which runs in O(n) time. The algorithm works by iterating over the array and at each step, calculating the maximum sum ending at that position, and keeping track of the overall maximum.

Mathematically, if we denote the array elements as \(a_1, a_2, \dots, a_n\), we want to compute:

[ \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} a_k\right) ]

If \(n=0\) (i.e. an empty array), the answer is defined to be \(0\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array. If \(n = 0\), then there is no second line.

outputFormat

Output a single integer which is the sum of the contiguous subarray with the maximum sum. The output is written to standard output (stdout).

5
1 2 3 4 5

15