Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and output that sum. In other words, for an array \(a_1, a_2, \dots, a_n\), you need to compute

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

If the array is empty (i.e. \(n = 0\)), output 0. This problem can be solved efficiently using Kadane's algorithm.

Input: The input consists of two lines. The first line contains a single integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated integers.

Output: Output a single integer which is the maximum subarray sum.

inputFormat

The input is given from standard input in the following format:

1. An integer \(n\), representing the number of elements in the array.
2. A single line containing \(n\) space-separated integers.

outputFormat

Output to standard output a single integer, the maximum sum of any contiguous subarray of the given array. If \(n = 0\), output \(0\).

5
1 2 3 4 5

15